cf1073c 二分+二维前缀和

#include<bits/stdc++.h> using namespace std; #define maxn 200005 char s[maxn]; int tmp,n,x,y,sum[2][maxn]; map<char,int>mp; int judge(int mid){//能否在mid长度内修改完 for(int l=1;l+mid-1<=n;l++){ int r=l+mid-1; int Y=sum[0][n]-sum[0][r]+sum[0][l-1]; int X=sum[1][n]-sum[1][r]+sum[1][l-1]; int tot=abs(x-X)+abs(y-Y);//在区间[l,r]要走的距离 if(tot<=mid)return 1; } return 0; } int main(){ mp['U']=1,mp['D']=-1,mp['L']=-1,mp['R']=1; cin>>n>>s+1>>x>>y; tmp=abs(x)+abs(y); if(n<tmp || tmp%2!=n%2){ puts("-1"); return 0; } for(int i=1;i<=n;i++){ if(s[i]=='U'||s[i]=='D'){ sum[0][i]=sum[0][i-1]+mp[s[i]]; sum[1][i]=sum[1][i-1]; } else { sum[0][i]=sum[0][i-1]; sum[1][i]=sum[1][i-1]+mp[s[i]]; } } int ans=-1,l=0,r=n,mid; while(l<=r){ mid=l+r>>1; if(judge(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); }

 

转载于:https://www.cnblogs.com/zsben991126/p/10367170.html