Educational Codeforces Round 53 C Vasya and Robot (二分)

题意
有一个机器人，有四种指令，上下左右，最初机器人在$(0,0)$位置，你现在要去$(X,Y)$,你可以随意更改指令，现在让你更改指令下标的最大值-最小值最小 且 更改后的指令能够到达$(X,Y)$
思路
首先维护前缀和，之后二分区间m，区间起点表示的就是我们下标的最小值，区间终点表示的就是我们下标的最大值，换句话说就是我们可以更改$[i,i+m]$这一段区间任意指令，之后我们看看 $[1,i]$，$[i+m+1,n]$的值和我们的终点$(X,Y)$差多少，其实就是我们现在需要多少次操作可以让其达到$(X,Y)$，之后我们看看我们需要更改的次数和我$m$d的大小，如果满足条件的话我们就缩小区间，之后我们二分去取最小值就好了。
代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int X[maxn] , Y[maxn];
int n , x
, y;
bool judge(int m)
{
for(int i = 1 ; i + m - 1<= n ; i++)
{
int tx = X[i-1] + X[n] - X[i+m-1];
int ty = Y[i-1] + Y[n] - Y[i+m-1];
tx = abs(x - tx); // 需要更改的x坐标 
ty = abs(y - ty); // 需要更改的y坐标 
if(tx + ty <= m && ((m - tx - ty)%2 == 0)) return true; // 如果总的更改次数小于区间长度，(m - tx - ty) 表示的是我们改完之后剩下来的值，如果他们是偶数就表示我们可以抵消掉 
}
return false;
}
int main()
{
string ch;
scanf("%d",&n);
cin>>ch;
scanf("%d%d",&x,&y);
X[0] = 0 , Y[0] = 0;
for(int i = 0 ; i < n ; i++)
{
int p = 0 , q = 0 ;
if(ch[i] == 'R') p = 1;
else if(ch[i] == 'L') p = -1;
if(ch[i] == 'D') q = -1;
else if(ch[i] == 'U') q = 1;
X[i+1] = X[i] + p , Y[i+1] = Y[i] + q;
}
int l = 0 , r = n , ans = -1;
while(l <= r)
{
int m = (l+r)>>1;
if(judge(m)) ans = m , r = m - 1;
else l = m + 1;
}
cout<<ans<<endl;
}

最后

以上就是精明草莓为你收集整理的Educational Codeforces Round 53 C Vasya and Robot (二分)的全部内容，希望文章能够帮你解决Educational Codeforces Round 53 C Vasya and Robot (二分)所遇到的程序开发问题。

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