题解 CF1117C 【Magic Ship】

开始新的记忆 · 2019-09-22 10:27:05 · 题解

题目大意：现在有一艘船，告诉你它的位置和终点的位置，并告诉你以n天为一个周期的风向，每天船都会往当天的风向走一个单位距离，你还可以操控船任意走一个单位距离（可不走），求最短多少天可以到达终点。

大致思路：一般看到答案是最大最小值就会想到二分答案。我们可以先用前缀和来维护一下当走了i天后，船因为风向而移动的距离，然后再在二分中如下判断（假设用了a天）：

1.先将船的初始坐标加上a/n个周期和a%n天的行驶距离。

2.判断当前与终点的曼哈顿距离是否小于等于n即可。

PS：二分别写错，如果满足或者不满足，le和ri总归不会取mid code：

#include<bits/stdc++.h>
using namespace std;
int ans[100010][2],n;

struct node{
    int x,y;
} be,en;

int main()
{   cin>>be.x>>be.y>>en.x>>en.y>>n;
    int xx=en.x-be.x,yy=en.y-be.y;
    for(int i=1;i<=n;++i)
    {
        char hh[2];
        cin>>hh[0];
        ans[i][0]=ans[i-1][0];
        ans[i][1]=ans[i-1][1];
        if(hh[0]=='U')
            ++ans[i][1];
        else if(hh[0]=='D')
            --ans[i][1];
        else if(hh[0]=='R')
            ++ans[i][0];
        else if(hh[0]=='L')
            --ans[i][0];
    }
    long long le=0,ri=1e18;
    while(ri>=le)
    {
        long long mid=(le+ri)>>1,t,tt;
        t=mid/n*ans[n][0]+ans[mid%n][0];
        long long tx=xx-t;
        tt=mid/n*ans[n][1]+ans[mid%n][1];
        long long ty=yy-tt;
        if(fabs(tx)+fabs(ty)<=mid)
            ri=mid-1;
        else 
            le=mid+1;
    }
    if(le<=1e18)
        cout<<le<<endl;
    else 
        cout<<-1<<endl;
    return 0;
}