A725[CSP-S 2020] 贪吃蛇

比赛时能做出来这题的都是神仙，因为他和蛇一样聪明！ 本篇题解的主要思路是参考sll学长的视频讲解的，在这里orz！

设所有蛇的实力为 a
1
​
,a
2
​
…a
n
​
，a
1
​
最小， a
n
​
最大。下面我们分情况讨论最大的蛇是否选择吃：

Case1：当前最强的蛇吃了最弱的蛇之后没有变成最弱的蛇

（结论一）**如果当前最强的蛇吃了最弱的蛇之后没有变成最弱的蛇，它一定会选择吃！**证明如下：

如果它吃完以后仍然是最大的蛇，不吃白不吃
否则，下一个最大的蛇为 a
n−1
​
，下一个最小的蛇为 a
2
​
。因为 a
n
​
≥a
n−1
​
，a
2
​
≥a
1
​
，所以 a
n
​
−a
1
​
≥a
n−1
​
−a
2
​
。如果 a
n−1
​
选择吃，那么它吃完后会比 a
n
​
吃完后更小，也就是说，它如果死也会死在 a
n
​
之前，由于它会尽量不死，所以 a
n
​
也不会死；如果 a
n−1
​
选择不吃，那么决斗结束， a
n
​
仍然安全。
Case2：当前最强的蛇吃了最弱的蛇之后变成了最弱的蛇

显然~~(废话)~~ ，如果它吃完以后，在之后的决斗中不会死，它就吃；换句话说，（结论二）在轮到它死之前，已经有蛇选择结束决斗，它就吃。

根据以上两个结论，我们可以得到本题的基本思路：

步骤一 ：我们先不考虑 Case2，假设所有的蛇都不聪明，按照 Case1 进行正向模拟一遍，记录每一轮中吃的蛇和被吃的蛇（即最大值 mx
i
​
和最小值 mi
i
​
）。显然的做法是用 set 维护。

步骤二：再考虑 Case2。记 dead
i
​
表示第 i 条蛇死的时间。从后往前，替每一轮中的蛇决定它是否要吃。从后往前是因为每条蛇当前是否选择结束游戏，是要根据它之后是否被吃判断的（结论二）。记 ans 表示决斗会在哪一轮结束。如果 dead
mx
i
​

​
<ans ，那么结束，ans=i。最终答案即为 n−ans+1 。

以上做法的复杂度瓶颈在于步骤一的模拟中需要用到 set ，每次取出最大最小值复杂度为 O(logn) ，我们希望把这一操作的复杂度降为 O(1)。看到题目中说保证每组数据（包括所有修改完成后的）的 a
i
​
以不降顺序排列，我们考虑用队列代替 set 维护，重新思考 Case1 和 Case2 中隐含的单调性。

设 w=a
n
​
−a
1
​
。我们维护两个队列， q1 中存原来的蛇，q2 中存每次新得到的蛇。

**Case1：**如果 w>a
n−1
​
，那么下一次的最大值为 w ，w−a
2
​
<w；否则w>a
n−1
​
−a
2
​
。满足单调性。（其实就是上面对结论一的证明）

Case2： w 就是下一次被吃掉的蛇。所以队列中始终只有一个元素，显然满足单调性。

根据上面的分析， 如果只有 Case1 或 Case2 ， q2 都是单调的。但如果 Case1 和 Case2 交替出现呢？

如果一串 Case1 后跟一串 Case2 ，Case2 会反复进出队，队里以前的元素不会用到
如果一串 Case2 后遇到一个 Case1，确实可能会不满足单调性。**但是！这次的 Case1 被吃掉的是上次 Case2 中选择吃蛇的蛇，既然它这次被吃了，那么因为它足够聪明，它上一次就不会选择吃！也就是说，这是一个边界条件，决斗在这之前就结束啦！**因此，不满足单调性也是没有关系的。
综上：q1 和 q2 都是满足单调性的。所以我们可以用两个 deque 代替 set，复杂度就降为 O(Tn) 了。具体实现细节可以看代码。

这道题我从学习解法，写代码，到写完这篇题解，花了整整一下午时间。这也是我写过的最长且最详细的一篇题解。希望大家和以后再回来看这篇题解的我都能看懂吧。

#include<bits/stdc++.h>
#define inl inline
using namespace std;
namespace FGF
{
int n,m;
const int N=1e6+5;
int b[N],a[N],q[N],de[N],h,t,st,ed,fl,end;
struct Node{
int mx,mi;
Node(){};
Node(int _mx,int _mi):mx(_mx),mi(_mi){};
}c[N];
int read()
{
int s=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
return s;
}
inl int getcm()//查找次小值
{
int mi;
if(st>ed)mi=q[t];
else if(h>t)mi=st;
else if(a[st]<a[q[t]]||(a[st]==a[q[t]]&&st<q[t]))mi=st;
else mi=q[t];
return mi;
}
inl int getmi()//取出最小值
{
int mi;
if(st>ed)mi=q[t],t--;
else if(h>t)mi=st,st++;
else if(a[st]<a[q[t]]||(a[st]==a[q[t]]&&st<q[t]))mi=st,st++;
else mi=q[t],t--;
return mi;
}
inl int getmx()//取出最大值
{
int mx;
if(st>ed)mx=q[h],h++;
else if(h>t)mx=ed,ed--;
else if(a[ed]>a[q[h]]||(a[ed]==a[q[h]]&&ed>q[h]))mx=ed,ed--;
else mx=q[h],h++;
return mx;
}
void solve()
{//这里我直接将a数组当q1用了
h=1,t=0,st=1,ed=n,fl=0,end=n-1;
for(int i=1;i<n;i++)//决斗最多进行n-1轮
{
int mx=getmx(),mi=getmi(),cm=getcm();
a[mx]-=a[mi];
q[t]=mx;//把新得到的值放入q2
c[i].mx=mx,c[i].mi=mi;
if(a[mx]>a[cm]||(a[mx]==a[cm]&&mx>cm))
{
if(fl)//一串Case2后跟了一个Case1，决斗结束
{
end=i;
break;
}
}
else fl=i;//记录一下Case2出现过了
}
for(int i=1;i<=n;i)de[i]=end+1;//初始化dead数组
de[c[end].mi]=end;
int ans=end+1;
for(int i=end-1;i;i--)
{
if(de[c[i].mx]<ans)ans=i;
de[c[i].mi]=i;
}
printf("%d\n",n-ans+1);
}
void work()
{
int T=read();n=read();
for(int i=1;i<=n;i++)
b[i]=a[i]=read();
solve();
for(int i=2;i<=T;i++)
{
int k=read();
for(int j=1;j<=n;j++)a[j]=b[j];
for(int j=1;j<=k;j++)
{
int x=read(),y=read();
b[x]=a[x]=y;
}
solve();
}
}
}
int main()
{
FGF::work();
return 0;
}

洛谷同步更新