跳石头———经典二分
可能是今天状态不好,一个很简单的二分,挺早之前就ac过了,但是今天牛客遇到了,发现写不出来,说明当时还没搞懂。
题意不说了,这里就说一下几个点:
1.在什么情况下才可以搬掉石头?
应该是石头2到石头1的距离小于二分出的答案mid
的时候。为什么呢?因为mid
是二分出来的答案,也就是最短跳跃距离的最大值,既然他是最短跳跃距离的最大值,那么必然不能存在两个石头的距离小于mid,否则与mid矛盾。
2.ans的更新
二分算法的几个点,其中一个就是ans的更新,这题ans的更新条件就是搬掉的石头 要小于等于 可搬掉的石头数,听上去很简(sha)单(bi),实际上也很简单
溜了溜了 补作业去
1 | /* |