考虑到m的范围异常的大,本题极有可能是二分搜值。我们猜测一个值X,然后检验是否能在m次移动后,使得所有的元素都大于等于X。
移动的策略似乎很明显可以贪心。当我在0号位置的时候,如果还没有实现得分大于X,必然会通过先朝右再朝左的反复横跳d次,直至满足0号位置大于等于X。为什么只选择在0号和1号位置的反复横跳而不是更大的幅度?感觉没有必要。如果更大幅度的反复横跳,不仅在0号位置和1号位置上各自增加d次赋分,而且会在2号及之后的位置上也增加d次赋分,但这些赋分是否值得呢?不见得。因此,我们只需要老老实实每次做幅度为1的来回横跳即可。
综上,我们的算法是:当我们来到i时,查看在该位置是否已经超过了预期得分。如果没有,那就计算还需要几次赋分(假设记作d次)。然后就再做=>(i+1)=>i
的d次反复移动。在i位置上满足之后,再移动依次到i+1的位置上,此时注意我们已经在i+1的位置上得到了points[i+1]*(d+1)
的分数。然后重复上述的过程。
需要特别注意的边界逻辑有两个地方:
- 如果走到了最后一个位置,仍没有超过预期得分,那么只能进行“往左再往右”的反复横跳。
- 如果走到了倒数第二个位置,经过几次横跳之后,发现在此位置和下一个位置都已经满足了得分预期,那么最后一步可以不用再走了。