题目大意:

一个机器人从(0,0)出发,输入一段指令字符串,和机器人需要在指定步数后到达的终点,问如果机器人需要在指定步数内到达终点,那么需要对原指令字符串做出怎样的改变,假设改变 字符串的最大下标为maxindex,改变字符串的最小下标为minindex,输出最小的 maxindex-minindex+1,即,输出最小的改变字符串的区间长度(该区间内的字符不一定要全部发生改变)。

解题分析:

本题可用二分答案求解,先预处理得到x,y的前缀和,即原始指令字符串对x,y的改变所作出的贡献,然后就是二分答案了,二分最短区间的长度。当然,二分答案最重要的就是check()函数,枚举所有长度为mid的区间,利用前缀和计算出理论上该区间x,y恰好所需的改变,然后判断该区间是否能够符合,具体步骤见代码。

这里,关闭了cin,cout的缓冲读入,莫名其妙WA在了第一发,实在是不太明白;以后还是老老实实用scanf了

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,x,y;
char s[N];
int sx[N],sy[N];

int check(int m){
    for(int i=1;i+m-1<=n;i++){
        int xx=sx[n]-sx[i+m-1]+sx[i-1];     
        int yy=sy[n]-sy[i+m-1]+sy[i-1];
        int tx=x-xx;
        int ty=y-yy;
        if(abs(tx)+abs(ty)<=m && (m-abs(tx)-abs(ty))%2==0)
            return 1;
    }
    return 0;
}

int main(){
    //ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;scanf("%s",s+1);
    cin>>x>>y;
    sx[0]=0;sy[0]=0;
    for(int i=1;i<=n;i++){
        sx[i] = sx[i - 1] + (s[i] == 'L' ? -1 : (s[i] == 'R' ? 1 : 0));
        sy[i] = sy[i - 1] + (s[i] == 'D' ? -1 : (s[i] == 'U' ? 1 : 0));
    }
    int l=0,r=n;
    int ans=-1;
    while(l<=r){
        int mid=(r+l)>>1;
        if(check(mid))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    cout<<ans<<endl;
    //system("pause");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注