Educational Codeforces Round 53 (Rated for Div. 2) C. Vasya and Robot
题意：给出一段操作序列 和目的地 问修改（只可以更改 不可以删除或添加）该序列使得最后到达终点时 所进行的修改代价最小是多少
其中代价的定义是 终点序号-起点序号-1
思路：因为代价是终点序号减去起点序号 所以 在终点和起点之前 可以任意变换 则如果 x+y 和序列长度n的奇偶性相同 就一定可以到达
可以使用二分（二分好容易写炸啊！） 把（以1为起点） 【1，i】U[【i+len,n】最后到达的点记为x0,y0 而中间缺的就是可以修改的区间
这里不必要判断奇偶性 因为如果x0，y0是 和为奇的点，n总数为奇数 那目的地是奇点 则剩下的步数是偶点（因为x0,y0为奇点，走了奇数步）
奇数点到奇数点只需要偶数步数 所以奇偶性是一致的，不用判断 奇偶 其他情况同理 故只需要判断步数是否足够到达 也就是
abs(x-x0)+abs(y-y0)<=可修改区间长度 这就是剩余步数可以到达的充要条件
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000+10;
char s[maxn];
int dx[maxn],dy[maxn];
int main(){
int n,x,y;
cin>>n>>s>>x>>y;
if(n<abs(x)+abs(y)||(n&1)!=((abs(x+y))&1)){
cout<<-1;return 0;
}
for(int i=0;i<n;i++){//预处理以计算x0,y0
dx[i+1]=dx[i];
dy[i+1]=dy[i];
if(s[i]=='U'){
dy[i+1]++;
}
if(s[i]=='D'){
dy[i+1]--;
}
if(s[i]=='L'){
dx[i+1]--;
}
if(s[i]=='R'){
dx[i+1]++;
}
}
int ans=INT_MAX;
for(int i=0;i<=n;i++){//枚举开始修改的起点
int start=i+1,end=n+2;
while(start!=end){
int mid=(start+end)/2;
int tempx=dx[i]+(dx[n]-dx[mid-1]),tempy=dy[i]+(dy[n]-dy[mid-1]);//计算到达的x0,y0
if(abs(tempx-x)+abs(tempy-y)<=mid-i-1)
end=mid;
else start=mid+1;
}
if(start!=n+2){
ans=min(ans,start-i-1);
}
}
cout<<ans<<endl;
}