[Codeforces]1073C Vasya and Robot(二分和前缀和）

分析：对区间长度进行二分查找。
先对x，y都做一下预处理求前缀和，即原始指令字符串对x,y的改变所作出的贡献。二分区间长度，并检查这个长度是否能够满足题意，利用前缀和计算出理论上该区间x,y恰好所需的改变，然后怎样算满足题意呢？首先需要理论上所需的贡献值小于等于这个区间的长度，其次，区间t=长度-理论值应该是个偶数，因为t显然是多余的，所以剩下位的字符如果是偶数，那么就可以让其走的路程两两抵消，从而达到刚好到达终点的效果。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define maxn 210000
typedef long long ll;
using namespace std;
ll n,ex,ey,flag=0;
ll fx[maxn],fy[maxn];
char ss;
bool check(ll len){
    for(int i=1;i+len-1<=n;i++){
    ll xx=fx[i+len-1]-fx[i-1];ll yy=fy[i+len-1]-fy[i-1];ll num=abs(ex-(fx[n]-xx))+abs(ey-(fy[n]-yy));if(num<=len&&(len-num)%2==0){
    flag=1;return true;}}return false;
}
int main()
{
    std::ios::sync_with_stdio(false);cin>>n;// cin>>ss;//计算出前缀和，算出对坐标改变的贡献度for(int i=1;i<=n;i++){
    cin>>ss;if(ss=='R'){
    fx[i]=fx[i-1]+1;fy[i]=fy[i-1];}if(ss=='L') {
    fx[i]=fx[i-1]-1;fy[i]=fy[i-1];}if(ss=='U') {
    fy[i]=fy[i-1]+1;fx[i]=fx[i-1];}if (ss=='D'){
    fy[i]=fy[i-1]-1;fx[i]=fx[i-1];}}cin>>ex>>ey;if(ex==fx[n]&&ey==fy[n]){
    cout<<"0"<<endl;return 0;}//二分查找区间ll l=0,r=n+1,mid;while(l<r){
    mid=(l+r)/2;if(check(mid)){
    r=mid;}else{
    l=mid+1;}}if(!flag) cout<<"-1"<<endl;else cout<<l<<endl;return 0;
}