题解 CF1117C 【Magic Ship】

· · 题解

我的博客网址

题目描述

平面直角坐标系上有一只小船，现在想从 (x_1,y_1) 去 (x_2,y_2) 。每时刻都有风，会把船往对应的风向吹一个单位（比如北风会把船往南吹），风是循环的，吹完s_1单位时间 就又会从s_1开始。船在每一时刻都可以向指定方向移动一个单位。求船到目的地的最少时间，如果不能到达输出 -1 。

输入格式

第一行为(x_1,y_1) 第二行为(x_2,y_2) 第三行为正整数 n， 第四行为风的方向，U/D/L/R表示风把船往上/下/左/右吹。

输出格式

共一行，表示最少时间。不能到达输出 -1 。

这里需要一点想象力:一边走一边吹，相当于先让风吹完再走

于是，我们有了这样的思(xiang)路(fa): 二分答案（行走时间)，判断这里被风吹走后的距离是否小于mid

bool check(LL mid)
{
    LL x = bx + sum['R'][n] * (mid / n) + sum['R'][mid % n] - sum['L'][n] * (mid / n) - sum['L'][mid % n];
    LL y = by + sum['U'][n] * (mid / n) + sum['U'][mid % n] - sum['D'][n] * (mid / n) - sum['D'][mid % n];
    return dist(x, y, ex, ey) <= mid;
}

一些细节 Anything\ else

  1. 常数优化sum['U'][i] = sum['U'][i - 1] + (c == 'U');\\前缀和
  2. 为了避免奇葩的字符问题，我们可以使用一个函数readchar
    char readchar()
{
 char c = getchar();
 while (c<'A' || c > 'Z')c = getchar();
 return c;
}
  3. 不是欧几里得距离，是曼哈顿距离!

完整代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 20;
typedef long long LL;
int bx, by, ex, ey;
char c; int n;
char readchar()
{
    char c = getchar();
    while (c<'A' || c > 'Z')c = getchar();
    return c;
}
LL sum[256][maxn];
LL dist(LL x1, LL y1, LL x2, LL y2)
{
    return llabs(x1 - x2) + llabs(y1 - y2);
}
bool check(LL mid)
{
    LL x = bx + sum['R'][n] * (mid / n) + sum['R'][mid % n] - sum['L'][n] * (mid / n) - sum['L'][mid % n];
    LL y = by + sum['U'][n] * (mid / n) + sum['U'][mid % n] - sum['D'][n] * (mid / n) - sum['D'][mid % n];
    return dist(x, y, ex, ey) <= mid;
}
inline int read()
{
    int x = 0, f = 1; char c = getchar();
    while (c<'0' || c>'9') { if (c == '-')f = -1; else f = 1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
    return x * f;
}
int main()
{
    bx = read(); by = read(); ex = read(); ey = read(); n = read();
    for (int i = 1; i <= n; i++)
    {
        c = readchar();
        sum['U'][i] = sum['U'][i - 1] + (c == 'U');
        sum['D'][i] = sum['D'][i - 1] + (c == 'D');
        sum['L'][i] = sum['L'][i - 1] + (c == 'L');
        sum['R'][i] = sum['R'][i - 1] + (c == 'R');
    }
    LL l = 0, r = 1e14 ,ans=-1;
    while (l <= r)
    {
        LL mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid - 1; ans = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans;
}