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;
}