CF-1117C-Magic Ship

  • 二分
    C - Magic Ship GNU C++11 Accepted 31 ms 1700 KB
    #include "bits/stdc++.h"
    using namespace std;
    typedef long long LL;
    typedef pair<LL, LL> PLL;
    const int MAXN = 1e5 + 5;
    PLL arr[MAXN];
    char s[MAXN];
    int main() {
        int n; 
        LL x1, x2, y1, y2;
        scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        scanf("%d%s", &n, s + 1);
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i - 1];
            switch(s[i]) {
                case 'U' : arr[i].second++; break;
                case 'D' : arr[i].second--; break;
                case 'L' : arr[i].first--; break;
                case 'R' : arr[i].first++; break;
            }
        }
        LL l = 0, r = 3e14, mid;
        while (r - l > 1) {
            mid = l + r >> 1;
            LL x, y;
            // 求出船不动任风吹mid天之后的船的坐标 
            x = x1 + mid / n * arr[n].first + arr[mid % n].first;
            y = y1 + mid / n * arr[n].second + arr[mid % n].second;
            // 如果距离终点mid以内,那么每天一步可以到达,否则无法到达 
            if (abs(y - y2) + abs(x - x2) <= mid) {
                r = mid;
            } else {
                l = mid;
            }
        }
        printf("%lld\n", r == 3e14 ? -1 : r);
        return 0;
    }

     

上一篇:空中成像技术概述


下一篇:[Luogu2730] 魔板 Magic Squares