本文主要是介绍Div. 2 ，C. Vasya and Robot，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题目第一眼看并不是一个二分，仔细思考一下，要枚举长度，然后又要枚举起点，这里已经是O(n^2)的复杂度了，还要判断是否满足条件，如果预处理了，是能在O(1)的复杂度解决的。所以枚举长度这边可以用一个二分，这样复杂度就是O(nlogn)了，可以解决这个题目。
如何在O(n)的复杂度判断这个长度满不满足要求呢？
枚举起点就要O(n)了，接下来就是O(1)判断O不OK；预处理到第i个字母时往右往上偏移了几位，那么枚举到一段区间的时候，我们可以将那一段区间的操作全部撤销（反正全改，长度也是len），那么此时的位置移到目标点最少的操作num 就是现在的位置和终点在X轴上的偏移量+Y轴上的偏移量，如果len>num,那么len-num一定要是偶数，这样上下左右才可以抵消。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ex,ey;
const int maxn=2e6+5;
struct X{ll r,u;
}f[maxn];
bool flag=0;
bool pd(int len){for(int i=1;i+len-1<=n;++i){ll rr=f[i+len-1].r-f[i-1].r,uu=f[i+len-1].u-f[i-1].u;//区间r和u的偏移量ll num=abs(ex-(f[n].r-rr))+abs(ey-(f[n].u-uu));//所需要的最小操作数if(len>=num&&(len-num)%2==0){flag=1;//说明可以走到终点return 1;}}return 0;
}
int main(){scanf("%lld",&n);getchar();f[0].r=0,f[0].u=0;char tmp;for(int i=1;i<=n;++i){scanf("%c",&tmp);//预处理if(tmp=='R') f[i].r=f[i-1].r+1,f[i].u=f[i-1].u;if(tmp=='L') f[i].r=f[i-1].r-1,f[i].u=f[i-1].u;if(tmp=='U') f[i].u=f[i-1].u+1,f[i].r=f[i-1].r;if(tmp=='D') f[i].u=f[i-1].u-1,f[i].r=f[i-1].r;}getchar();scanf("%lld%lld",&ex,&ey);if(f[n].r==ex&&f[n].u==ey) cout<<0<<endl;else{int le=0,ri=n+1;while(ri>le){int mid=(le+ri)/2;if(pd(mid)) ri=mid;else le=mid+1;}if(!flag) cout<<-1<<endl;else cout<<le<<endl;}return 0;
}
这篇关于Div. 2 ，C. Vasya and Robot的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
