cf 1073c 二分 思维

题意：给定一个长为n的串，代表机器人的行走方式，要求机器人到达(x,y)点

　　将原串的子串修改，求最小的子串的长度

 

思路：

很容易知道如何到达x,y点    假设 res= abs(x)+abs(y);那么 n>=res && (n-res)%2==0

那么如何寻找一个子串呢？

用二分枚举长度len，然后枚举所有长度为Len的子串看看有没有可能满足

　　　枚举子串已经用O(n)的复杂度了

　　  判断的条件就是剩余到达(nx,ny) 用长度为Len的子串是否能到(nx-x,ny-y)

　　　这样处理的话，处理前缀 就可以O(1)求Nx,ny了  

　　总时间 n*logn

 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
const int N
=2e5+4;
const ll mod = 2e9+7;
const int INF = 1e9+3;
const ll LINF = 1e18+3;
int n; ll x,y;
int R[N],U[N];
char s[N];
bool can(int len){
for(int i=1;i<=n-len+1;++i){
int nx,ny;
//[i,i+len-1]
nx = R[i-1] + R[n]-R[i+len-1];
ny = U[i-1] + U[n]-U[i+len-1];
int need = abs(x-nx)+abs(y-ny);
if(len>=need && (len-need)%2==0)return true;
}
return false;
}
int main(){
cin>>n;
scanf("%s",s+1);
cin>>x>>y;
for(int i=1;i<=n;++i){
R[i]=R[i-1];U[i]=U[i-1];
if(s[i]=='R')R[i]+=1;
if(s[i]=='L')R[i]+=-1;
if(s[i]=='U')U[i]+=1;
if(s[i]=='D')U[i]+=-1;
}
int res= abs(x)+abs(y);
if(n>=res && (n-res)%2==0){
int l=0,r= n;
int ans = n;
while(l<=r){
int mid =(l+r)/2;
if(can(mid)){
r = mid-1;
ans = min(ans,mid);
}
else {
l= mid+1;
}
}
cout<<ans<<endl;
}
else {
cout<<-1<<endl;
}
return 0;
}