模拟+贪心(100pts)

算法分析

当这个能力强的蛇如果吃了以后不是最弱的，那么它一定会吃，否则的话，我们需要去判断他变成最弱的以后会不会被吃。

每次吃了以后生成的新的蛇一定是从大到小的，差值是一个小的减去了一个大的，这样我们就可以用两个队列来维护了。

#include<bits/stdc++.h>
using namespace std;
const int N=1000010,INF=2e9;
int n;
int w[N];
typedef pair<int,int> PII;
#define v first
#define id second
PII q1[N],q2[N];
int hh1,hh2,tt1,tt2;
PII get_max()
{
	PII res={-1,-1};
	if(hh1<=tt1) res=q1[tt1]; //找到最大值 
	if(hh2<=tt2&&q2[tt2]>res) res=q2[tt2];
	if(hh1<=tt1&&res==q1[tt1]) tt1--; //删除最大值 
	else tt2--;
	return res; //返回最大值 
}
PII get_min(bool del=true)
{
	PII res={INF,INF};
	if(hh1<=tt1) res=q1[hh1]; //找到最小值 
	if(hh2<=tt2&&res>q2[hh2]) res=q2[hh2];
	if(del)	 //删除最小值 
	{
		if(hh1<=tt1&&res==q1[hh1]) hh1++;
		else hh2++;
	}
	return res;
} 
bool check(int cnt)
{
	if(cnt==1) return false; //自己不能吃自己 
	if(cnt==2) return true; //吃了以后还是最大的
	PII strong=get_max(),weak=get_min();
	strong.v-=weak.v;
	if(strong>get_min(false)) return true ;
	//吃了以后不是最小值的就还可以吃
	//吃了以后变成最小的
	q2[--hh2]=strong; //加入队列之中
	if(check(cnt-1)) return false; //会被吃 
	return true;  //不会被吃 
}
int work()
{
	hh1=0,tt1=-1,hh2=n,tt2=n-1;
	for(int i=1;i<=n;i++)
	{
		q1[++tt1]={w[i],i};
	}
	int res=n;
	for(int i=0;i<n-1;i++)
	{
		PII strong=get_max(),weak=get_min();
		strong.v-=weak.v;
		res--;//少了一个
		q2[--hh2]=strong;//加入队列之中
		if(strong==get_min(false)) break;
		//说明是最小的，那么需要判断会不会被吃 
	}
	if(check(res)) res++; //会被吃，就不能吃，存活的数目就多一条
	return res;
}
int main()
{
	int T;
	cin>>T;
	for(int i=1;i<=T;i++)
	{
		if(i==1)
		{
			cin>>n;
			for(int i=1;i<=n;i++)  //获取原始数据       
			{
				cin>>w[i];	
			}	
		}	
		else //多组数据
		{
			int m;
			cin>>m;
			while(m--)
			{
				int x,y;
				cin>>x>>y;
				w[x]=y;
			}
		}
		cout<<work()<<endl;
	} 
	return 0;
}