本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-16 20:08:54
难度：$\color{black}\text{NOI/NOI+/CTSC}$
$\color{green}\text{AC算法：}$贪心，队列
题目分析：
题面不用解释,就是让回答有多少蛇将存活。
显然，蛇保命的优先级最高，在自身能保命的前提下尽可能多的弄死别的蛇 （让我想起了海盗分金问题）
设当前蛇为 $dq$
可以分两种情况讨论：
1、 $dq$ 吃了最弱的蛇之后不会变成最弱的蛇
2、 $dq$ 吃了最弱的蛇之后会变成最弱的蛇
对于情况一：
显然可以大胆吃
对于情况二：
设 $dq$ 进食后，新的老大为 $dq2$。此时 $dq2$也遇到了相同两种情况。如果 $dq2$ 进食之后不会变成最弱的蛇，那么 $dq2$ 一定会吃掉 $dq$，$dq$ 不应该进食。如果 $dq2$ 进食之后会变成最弱的，那么那就再看 $dq3$ 的情况........就这样递归下去。直到有一条蛇可以吃或者只剩下两条蛇。此时设第 $i$ 个蛇可以放心吃。那么第 $i-1$ 条蛇就不应该吃，否则将在下一轮被吃掉。而第 $i-2$ 条蛇可以吃，因为它知道第 $i-1$ 条蛇不敢吃它。
现在就有了一个结论：对于第 $i$ 轮递归的蛇可以大胆吃，如果 $i$ 为奇数，那么当前蛇就不应该吃；如果 $i$ 为偶数，那么当前蛇就可以大胆吃，然后转化为 $i$ 为奇数的稳定状态。（当然如果只有两条蛇那么只有一条蛇可以存活）
题目分析完毕，剩余的在注释里。
AC代码：
#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e6+5;
#define reg register
int a[maxn];
int t;
int n;
int k;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-1;
}
if(x>9)write(x\/10);
putchar(x%10+'0');
}
int main()
{
t=read();
int testcnt=0;
while(t--)
{
testcnt++;
int ans=0;
if(testcnt==1)
{
n=read();
for(reg int i=1;i<=n;i++)
{
a[i]=read();
}
}
if(testcnt>1)
{
k=read();
reg int x,y;
for(reg int i=1;i<=k;i++)
{
x=read();
y=read();
a[x]=y;
}
}
deque<pair<int,int> > que1;
deque<pair<int,int> > que2;
for(reg int i=1;i<=n;i++)
{
que1.emplace_back(make_pair(a[i],i));
}
while(1)
{
if(que1.size()+que2.size()==2)
{
ans=1;
break;
}
\/\/取出最弱
int y=que1.front().first;
que1.pop_front();
\/\/取出最强
int x;
int bianhao;\/\/最强者编号
if(que2.empty()||(!que1.empty()&&que1.back()>que2.back()))
{\/\/如果que1不空且它的最后一个元素是两个队列最大的才行
\/\/但是如果que2没有就只能选que1
x=que1.back().first;
bianhao=que1.back().second;
que1.pop_back();
}
else{
x=que2.back().first;
bianhao=que2.back().second;
que2.pop_back();
}
pair<int,int> xianzai=make_pair(x-y,bianhao);
if(que1.empty()||xianzai<=que1.front())\/\/pair自动比较第一个参数
{\/\/最强蛇进食之后变成了最弱蛇
ans=que1.size()+que2.size()+2;
\/\/先假设不吃
int count=0;
\/\/第几轮递归
while(1)
{
count++;
if(que1.size()+que2.size()+1==2)
{
if(!(count&1))ans--;
\/\/可以发现，当轮数为偶数时，当前最强才能放心吃
break;
}
\/\/重新选择当前最强递归下去
if(que2.empty()||!que1.empty()&&que1.back()>que2.back())
{ \/\/如果que1不空且它的最后一个元素是两个队列最大的才行
\/\/但是如果que2没有就只能选que1
x=que1.back().first;
bianhao=que1.back().second;
que1.pop_back();
}
else{
x=que2.back().first;
bianhao=que2.back().second;
que2.pop_back();
}
xianzai=make_pair(x-xianzai.first,bianhao);\/\/之前的最强已经是最弱了，让现在的最强进食
if(!((que1.empty()||xianzai<que1.front())&&(que2.empty()||xianzai<que2.front())))
{\/\/如果不是最弱的，那么看看能不能吃
if(!(count&1))
{
ans--;
}
break;
}
}
break;
}
else
{
que2.emplace_front(xianzai);
\/\/如果吃掉后不是最弱，那么大胆吃！
}
}
write(ans);
putchar('\n');
}
return 0;
}
。
鲁ICP备2025150228号