CF1073C Vasya and Robot

朴灿烈づ我的快乐病毒、 2021-12-23 05:31 140阅读 0赞

CF题目难度普遍偏高啊……

一个乱搞的做法。因为代价为最大下标减去最小的下标，那么可以看做一个区间的修改。我们枚举选取的区间的右端点，不难发现满足条件的左端点必然是不降的。那么用一个指针移一下就好了

注意特判无解和答案为\\(0\\)的情况，时间复杂度\\(O(n)\\)（然而因为人傻常数大所以还跑不过\\(O(nlogn)\\)的）

//minamoto
    #include<bits/stdc++.h>
    #define rint register int
    #define GG return puts("-1"),0
    using namespace std;
    const int N=5e5+5;
    struct node{
        int x,y;
        node(){}
        node(int x,int y):x(x),y(y){}
        inline node operator +(const int &b)const{
            switch(b){
                case 0:return node(x-1,y);break;
                case 1:return node(x+1,y);break;
                case 2:return node(x,y-1);break;
                case 3:return node(x,y+1);break;
            }
        }
        inline node operator +(const node &b)const{return node(x+b.x,y+b.y);}
        inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
    }sum[N];
    char s[N];int val[105],n,ans=0x3f3f3f3f,x,y;
    inline int dis(int x,int y,int xx,int yy){return abs(x-xx)+abs(y-yy);}
    bool check(int l,int r){
        node res=sum[n]-sum[r]+sum[l-1];
        return dis(res.x,res.y,x,y)<=r-l+1;
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
        scanf("%d%s%d%d",&n,s+1,&x,&y);
        val['L']=0,val['R']=1,val['D']=2,val['U']=3;
        if(dis(0,0,x,y)>n||((dis(0,0,x,y)&1)!=(n&1)))GG;
        for(rint i=1;i<=n;++i)sum[i]=sum[i-1]+val[s[i]];
        if(sum[n].x==x&&sum[n].y==y)return puts("0"),0;
        for(rint i=1,j=1;i<=n;++i){
            while(j<i&&check(j+1,i))++j;
            if(check(j,i))ans=min(ans,i-j+1);
        }printf("%d\n",ans);return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/9994359.html