<题目链接>
题目大意：
一个机器人从(0,0)出发，输入一段指令字符串，和机器人需要在指定步数后到达的终点，问如果机器人需要在指定步数内到达终点，那么需要对原指令字符串做出怎样的改变，假设改变 字符串的最大下标为maxindex,改变字符串的最小下标为minindex，输出最小的 maxindex-minindex+1，即，输出最小的改变字符串的区间长度(该区间内的字符不一定要全部发生改变)。
解题分析：
本题可用二分答案求解，先预处理得到x,y的前缀和，即原始指令字符串对x,y的改变所作出的贡献，然后就是二分答案了，二分最短区间的长度。当然，二分答案最重要的就是check()函数，枚举所有长度为mid的区间，利用前缀和计算出理论上该区间x,y恰好所需的改变，然后判断该区间是否能够符合，具体步骤见代码。
#include <bits/stdc++.h>
using namespace std;
const int N =1e6+;
int n,x,y;
char s[N];
int sx[N],sy[N]; bool check(int m){
for(int i=;i+m-<=n;i++){ //枚举所有长度为m的区间
int xx=sx[n]-sx[i+m-]+sx[i-];
int yy=sy[n]-sy[i+m-]+sy[i-];
//得到不需要改变的区间中，对x,y的数值所作出的贡献
int tx=x-xx;
int ty=y-yy;
//求出该需要改变的区间中，x和y想要到达终点，所需恰好作出的贡献
if(abs(tx)+abs(ty)<=m && (m-abs(tx)-abs(ty))%==) //(abs(tx)+abs(ty)位字符做出使该人刚好到达终点的贡献，剩下位的字符如果是偶数，那么就可以让其走的路程两两抵消，从而达到刚好到达终点的效果)
return true;
}
return false;
}
int main(){
scanf("%d",&n);
scanf("%s",s+);
scanf("%d%d",&x,&y);
sx[]=;sy[]=;
for(int i=;i<=n;i++){
sx[i] = sx[i - ] + (s[i] == 'L' ? - : (s[i] == 'R' ? : ));
sy[i] = sy[i - ] + (s[i] == 'D' ? - : (s[i] == 'U' ? : ));
}
//求出按照原始序列走，x和y的前缀和
int l=,r=n;
int ans=-;
while(l<=r){ //二分答案，枚举需要改变的最短区间长度
int mid=(l+r)>>;
if(check(mid))ans=mid,r=mid-; //如果该区间长度符合，就继续二分,看更短的区间是否符合
else l=mid+;
}
if(ans==-)puts("-1");
else printf("%d\n",ans);
return ;
}
2018-10-27