「Codeforces 1117C」Magic Ship

Description

坐标系上有一只小船，现在想从 $(x_1,y_1)$ 去 $(x_2,y_2)$ 。每时刻都有风，会把船往对应的风向吹一个单位，风是循环的，吹完 $s_1 \sim s_n$ 就又会从 $s_1$ 开始。船在每一时刻都可以向指定方向移动一个单位。求船到目的地的最少时间，如果不能到达输出 -1 。$(1 \leq n \leq 10^5,0 \leq x_1,x_2,y_1,y_2 \leq 10^9)$

Source

[Luogu]CF1117C

[Codeforces]1117C

Solution

考虑 二分答案 。

首先要想到一个转化。虽然风吹与船行同时进行，但我们可以先让风吹完了再让船走。由于我们已经二分得到了时间，所以风吹完后小船的坐标我们是已知的（可以用前缀和预处理 $s_1 \sim s_n$ 前 $i$ 时刻每种风的数量），而小船到目的地的最短距离就是该坐标与目的地的 曼哈顿距离 。如果这个距离不超过时间，说明船是可以在规定的时间之内到达的。

二分的下界显然是 $0$，上界怎么算呢？如果风一直把船往与目的地相反的方向吹，只有一个时刻的风是相同方向的，那样经过 $n$ 时刻才能移动 $2$ 格，因此最坏情况下需要 $10^{14}$ 的时间。总时间复杂度为 $O(\log \max\{ans\})$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

inline void readChar(char &c) {
    for (c = getchar(); c != 'U' && c != 'D' && c != 'L' && c != 'R'; c = getchar());
}

const int MAXN = 1e5;
LL sx, sy, tx, ty, n, ans = -1;
int sum[100][MAXN + 5];
char d[MAXN + 5];

inline LL dist(LL x1, LL y1, LL x2, LL y2) {//曼哈顿距离 
    return abs(x1 - x2) + abs(y1 - y2);
}

inline bool check(LL p) {
    LL x = sx + sum['R'][n] * (p / n) + sum['R'][p % n] 
    - sum['L'][n] * (p / n) - sum['L'][p % n];//一共 p / n 次循环，多余的单独处理
    LL y = sy + sum['U'][n] * (p / n) + sum['U'][p % n] 
    - sum['D'][n] * (p / n) - sum['D'][p % n];
    return dist(x, y, tx, ty) <= p;//判断是否在能规定时间内到达目的地
}

int main() {
    read(sx), read(sy), read(tx), read(ty), read(n);
    for (int i = 1; i <= n; ++i) {
        readChar(d[i]);
        sum['R'][i] = sum['R'][i - 1] + (d[i] == 'R');
        sum['L'][i] = sum['L'][i - 1] + (d[i] == 'L');
        sum['U'][i] = sum['U'][i - 1] + (d[i] == 'U');
        sum['D'][i] = sum['D'][i - 1] + (d[i] == 'D');//前缀和预处理
    }
    for (LL l = 0, r = 1e14; l <= r; ) {//二分答案，注意上界
        LL mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1; 
            ans = mid;
        } else l = mid + 1;
    }
    write(ans);
    putchar('\n');
    return 0;
}