CF1117C 题解

ikunTLE · 2024-07-12 21:50:32 · 题解

题目传送门

思路

对于小船每一次移动的位置，我们可以用类似前缀和的思想预处理每一次小船的位置。接着就可以二分答案，对于每一次判断的数 mid，计算它新的坐标，并判断其曼哈顿距离是否 \le mid。

check 函数展示：

bool check(long long mid){
    //该代码中的px和py是预处理后的小船坐标位置
    long long sx=x1+px[n]*(mid/n)+px[mid%n];//计算新的x坐标
    long long sy=y1+py[n]*(mid/n)+py[mid%n];//计算新的y坐标
    return abs(sx-x2)+abs(sy-y2)<=mid;//判断它是否<=mid
}

注意事项

• 不开 long long 见祖宗。

• 二分的右边界一定要足够大，本人建议 2^{60}。