CF - 1073c Vasya and Robot

题目的大意大概是有一个机器人从(0,0)出发，根据给定的方向行走，然后给定一个坐标，让你改变最小的步数来使得机器人走到那里，如果无法到达输出-1.

思路：

先按原来的序列计算x,y的前缀和，然后二分，找出需要改变的最短区间长度，枚举所有的长度为m的区间，然后判断区间是否符合条件，若符合就进行二分，条件为改变区间的贡献值小于区间长度且剩余的个数为偶数个。代码如下：

#include<iostream>
#include<string>
#include<algorithm>
#define maxn 1000000
using namespace std;
char a[maxn];
int ax[maxn], ay[maxn];
int main()
{
int n, x, y;
cin>>n;
for(int i=1; i<=n; ++i)
cin>>a[i];
cin>>x>>y;
ax[0] = 0;
ay[0] = 0;
for(int i=1; i<=n; i++)
{
ax[i] = ax[i - 1] + (a[i] == 'L' ? -1 : (a[i] == 'R' ? 1 : 0));
ay[i] = ay[i - 1] + (a[i] == 'D' ? -1 : (a[i] == 'U' ? 1 : 0));
}
int l=0, r=n, ans=-1;
while(l<=r)
{
int mid = (l+r)/2;
int flag = false;
for(int i=1; i+mid-1<=n; ++i)
{
int xx = ax[n]-ax[i+mid-1]+ax[i-1];
int yy = ay[n]-ay[i+mid-1]+ay[i-1];
int tx = x- xx;
int ty = y -yy;
if(abs(tx)+abs(ty)<=mid && (mid-abs(tx)-abs(ty))%2==0)
{
ans = mid;
r = mid - 1;
flag = true;
break;
}
}
if(!flag)
l=mid+1;
}
if(ans == -1)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
return 0;
}

最后

以上就是神勇麦片为你收集整理的CF - 1073c Vasya and Robot的全部内容，希望文章能够帮你解决CF - 1073c Vasya and Robot所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。