Vasya and Robot

C. Vasya and Robot

关键算法：二分、前缀和

刚看到题的时候一点想法都没有...

先观察一下数据范围$(1≤n≤2⋅10^5)(−10^9≤x,y≤10^9) $

可以用两个数组\(x[i],y[i]\)来表示在\(i\)操作完之后的机器人的位置

for(int i=0;i<n;++i)
{
    if(s[i]=='U') y[i+1]=1;
    if(s[i]=='D') y[i+1]=-1;
    if(s[i]=='R') x[i+1]=1;
    if(s[i]=='L') x[i+1]=-1;
    x[i+1]+=x[i],y[i+1]+=y[i];
}

然后可以发现题目要求的是最大位置和最小位置之间的距离\(m\)（包括端点），而并没有对更改操作数有大小限制，那么我们只需知道在没有这一段操作的情况下将到达的点与目标终点之间相差的操作数\(dis\)与\(m\)能否满足\((dis<=mid,abs(dis-mid)\%2==0)\)这样一段关系即可。

代码：

// Created by CAD on 2020/1/12.
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int maxn=2e5+5;
int x[maxn],y[maxn];
int X,Y,n;
bool judge(int mid)
{
    for(int i=1;i<=n+1-mid;++i)
    {
        int j=i+mid-1;
        int dx=x[j]-x[i-1],dy=y[j]-y[i-1];
        int dis=abs(x[n]-dx-X)+abs(y[n]-dy-Y);
        if(dis<=mid&&abs(dis-mid)%2==0)
            return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    string s;   cin>>s;
    cin>>X>>Y;
    for(int i=0;i<n;++i)
    {
        if(s[i]=='U') y[i+1]=1;
        if(s[i]=='D') y[i+1]=-1;
        if(s[i]=='R') x[i+1]=1;
        if(s[i]=='L') x[i+1]=-1;
        x[i+1]+=x[i],y[i+1]+=y[i];
    }
    int l=0,r=n;
    int ans=inf;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid)) ans=min(ans,mid),r=mid-1;
        else l=mid+1;
    }
    if(ans==inf) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}