CSP-S 2020 贪吃蛇

7年OI一场空，一句assert见祖宗。

题解

考虑一条蛇什么时候会叫停。

如果它吃了之后不是最小的，那么下一个吃了之后一定比它小(指以id为第二关键字后)，死的一定比它早，那么可以直接吃，然后把问题交给下一条蛇即可。

如果吃了之后是最小的，那么下一个有可能吃它，那么它吃不吃就和下一条吃不吃相关，也就是和到之后第一次吃了不是最小的 的距离奇偶性相关了。

前面一部分显然满足后一个吃了之后比它小。后面(除了最后一次)也满足吃了之后会变成最小的。

那么再用一个队列，用类似「noip2016 蚯蚓」的方法维护即可。

时间复杂度$O(n)$，并且在$a_i$不满足不降的情况下应该也是对的。

然而我加了个错误的assert，然后就挂了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
int n;
int a[1000005];
namespace run{
    pii w1[1000005],w2[1000005];
    pii *l1,*r1,*l2,*r2;
    const pii inf(0x3f3f3f3f,0x3f3f3f3f),ind(-0x3f3f3f3f,-0x3f3f3f3f);
    pii mx1(){return l1<=r1?*l1:ind;}
    pii mn1(){return l1<=r1?*r1:inf;}
    pii mx2(){return l2<=r2?*l2:ind;}
    pii mn2(){return l2<=r2?*r2:inf;}
    int cnt,cur;
    bool add0(){
        if(~cur){cur^=1;}
        else{cur=0;}
        return 0;
    }
    bool add1(){
        if(~cur){cnt+=cur;return 1;}
        ++cnt;return 0;
    }
    void solve(){
        l2=w2+1;r2=w2;
        l1=w1+1;r1=w1+n;
        for(int i=1;i<=n;++i){
            w1[n+1-i].x=a[i];w1[n+1-i].y=i;    
        }
        cnt=0;cur=-1;
        int s=n;
        while(s>1){
            pii mx,mn;
            if(mx1()>mx2()){mx=mx1();++l1;}
            else{mx=mx2();++l2;}
            if(mn1()<mn2()){mn=mn1();--r1;}
            else{mn=mn2();--r2;}
            mx.x-=mn.x;
            --s;
            //assert(mx<mn2()); 这里显然是错的，因为从最小变成不是最小的时候不一定比第二小小。
            if(s>1 && mx<min(mn1(),mn2())){
                if(add0())return;
            }
            else{
                if(add1())return;
            }
            *(++r2)=mx;
/*            if(add0())return;
            if(add1())return;*/
        }
    }
    bool main(){
        solve();
        printf("%d\n",n-cnt);
        return 0;
    }
}
int main(){
    freopen("snakes.in","r",stdin);
    freopen("snakes.out","w",stdout);
    int t;
    scanf("%d",&t);
    for(int id=1;id<=t;++id){
        if(id==1){
            scanf("%d",&n);
            for(int i=1;i<=n;++i)scanf("%d",a+i);
        }
        else{
            int k,x;
            scanf("%d",&k);
            for(;k;--k){
                scanf("%d",&x);    
                scanf("%d",a+x);
            }
        }
        run::main();
    }
    return 0;
}