题解 CF1117C 【Magic Ship】

· · 题解

第一眼看题目像东南西北，再一看没有这么简单。

不过我们可以稍微利用那题的思路。

首先我们需要用前缀和数组处理每一天的移动情况。

因为如果在线求的话时间不够

因为是最小值，所以答案唯一，我们可以自然想到二分求解。

二分天数，求出每天的移动情况（风向与船行的最佳决策）

如果得到的最短曼哈顿距离小于等于当前的天数

便记录下答案，其实就是左边界。

注意这题是曼哈顿距离!!!

详情见代码注释：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
//IG NB!
using namespace std;
void read(ll &x)
{
     x=0;ll w=1;
     char ch=getchar();
     while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
     if(ch=='-')w=-1,ch=getchar();
     while(ch>='0'&&ch<='9')
     {x=(x<<1)+(x<<3)+ch-48,ch=getchar();}
     x*=w;
}
int mx(int a,int b){return a>b?a:b;}
int mn(int a,int b){return a<b?a:b;}
ll a,b,c,d,n,nx,ny,TX[100005],TY[100005];
char s[100005];
ll Abs(ll a){return a<0?-a:a;}
int main()
{
    read(a);read(b);
    read(c);read(d);
    read(n);
    ll x=c-a,y=d-b;//曼哈顿坐标距离
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='U')
        {
            TX[i]=TX[i-1];
            TY[i]=TY[i-1]+1;
        }
        else 
            if(s[i]=='D')
            {   
                TX[i]=TX[i-1];
                TY[i]=TY[i-1]-1;
            }
        else 
            if(s[i]=='L') 
            {
                TX[i]=TX[i-1]-1;
                TY[i]=TY[i-1];
            }
        else 
            if(s[i]=='R')
            {
                TX[i]=TX[i-1]+1;
                TY[i]=TY[i-1];
            }
    }//前缀和处理每天x，y轴的移动情况。
    ll l=0,r=1e18,LE=n;//r为最大边界，因为本题数据较大，所以开1e18
    while(r-l>=0)
    {
        ll Mi=(l+r)>>1;//二分天数
        ll tmp1,tmp2;
        tmp1=Mi/LE*TX[LE];
        tmp1+=TX[Mi%LE];
        ll tx=x-tmp1;
        tmp2=Mi/LE*TY[LE];
        tmp2+=TY[Mi%LE];
        ll ty=y-tmp2;//相当于check，预处理当天风向与移动的最优情况
        if(Abs(tx)+Abs(ty)<=Mi)//曼哈顿距离是否小于等于当前二分到的天数。
        {
            r=Mi-1;//边界-1
        }
        else 
        {
            l=Mi+1;//答案+1
        }
    }
    if(l<=1e18)printf("%I64d",l);//答案为l
    else printf("-1");//如果l未变，说明没有符合情况，则无解，输出-1
    putchar('\n');
    return 0;
}