【Educational Codeforces Round 53 (Rated for Div. 2)-C. Vasya and Robot】二分

Educational Codeforces Round 53 (Rated for Div. 2) C. Vasya and Robot

题意

$在二维平面上有一个机器人最开始在点(0,0)处$
$最终他要走到点(x,y)处,现在给出行动路线，有(L,R,U,D)四种走法$
$每次他可以修改某个区间内的走法，问需要修改的最小区间长度是多少$
$（区间内可以修改为任意走法，也可以不修改）$
$n<=2?10^5$

做法

$这个数据范围大概只能想二分，二分长度之后枚举每个点作为区间起点是否能走到(x,y)$
$check的过程就是先把区间之外的走法走完，得到(x1,y1)$
$再判断(x1,y1)与(x,y)的曼哈顿距离D$
$如果当前区间长度len>D而且（len?D)Mod2==0，就代表机器人可以通过当前区间走到(x,y)$
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endl
const int maxn = 2e5+10;
char s[maxn];
int x,y;
int n,sum[maxn][4];//U D L R
map<char,int> mp;
int n1,n2,n3,n4;
bool check(int mid)
{
    int sum1=0,sum2=0,sum3=0,sum4=0;for(int i=1;i<=n-mid+1;i++){
    sum1=sum[i-1][0]+sum[n][0]-sum[i+mid-1][0];sum2=sum[i-1][1]+sum[n][1]-sum[i+mid-1][1];sum3=sum[i-1][2]+sum[n][2]-sum[i+mid-1][2];sum4=sum[i-1][3]+sum[n][3]-sum[i+mid-1][3];int xx=0,yy=0;n1=0,n2=0,n3=0,n4=0;xx+=(sum4-sum3);yy+=(sum1-sum2);if(xx>=x) n3=xx-x;else n4=x-xx;if(yy>=y) n2=yy-y;else n1=y-yy;if(n1+n2+n3+n4<=mid&&(mid-n1-n2-n3-n4)%2==0) return true;}return false;
}
int main()
{
    mp['U']=0;mp['D']=1;mp['L']=2;mp['R']=3;scanf("%d%s",&n,s+1);for(int i=1;i<=n;i++){
    sum[i][0]=sum[i-1][0];sum[i][1]=sum[i-1][1];sum[i][2]=sum[i-1][2];sum[i][3]=sum[i-1][3];sum[i][mp[s[i]]]++;}scanf("%d%d",&x,&y);int l=0,r=n,mid;while(l<=r){
    int mid=(l+r)/2;if(check(mid)) r=mid-1;else l=mid+1;}if(l==n+1) printf("-1\n");else printf("%d\n",l);return 0;
}