P7078 做题笔记

显然的贪心题。

首先，如果一条蛇吃了蛇之后自己不是最弱的，一定会吃。

证明：假设蛇的实力数组 \(a\) 单调递增，一共还剩 \(k\) 条蛇。

显然有 \(a_{k-1}-a_2<a_k-a_1\)，也就是说，无论如何吃了之后都不会变成最弱蛇，所以一定吃。

然后考虑吃了之后会变成最弱蛇的情况。

首先来看 2023 年天元公学邀请赛的一道初赛题：

有 \(n\) 只青蛙，\(1\) 只天鹅，每只青蛙按编号依次选择吃或不吃天鹅，如果吃了，自己将变成天鹅，否则无事发生，游戏结束。假设青蛙足够聪明，问当 \(n\) 为下列选项中哪一个数时，天鹅会被吃掉。

A.4 B.6 C.9 D.12

我们发现这道题和吃了之后会变成最弱蛇的情况有异曲同工之处。我们不妨用归纳法来做一做这道初赛题。

首先，如果只有一只青蛙，肯定吃。

如果有两只青蛙，第一只青蛙吃了之后就变成了一只青蛙的状态，就导致第一只青蛙会被吃掉，所以第一只青蛙不会吃。

如果有三只青蛙，第一只青蛙会吃，因为如果吃了之后，第二只青蛙不会选择吃掉天鹅（因为如果选择吃自己会被吃掉），所以第一只青蛙会吃。

至此，我们的结论就出来了，当 \(n \equiv 1 \pmod 2\) 时，天鹅会被吃掉，否则不会被吃。并且最多只吃一轮。

那么我们只要模拟一下，就能决定吃或不吃了。

现在的问题是，如何维护数组有序。

用堆复杂度太高，无法获得满分。于是我们用双端队列进行构造，会发现可以简单的维护有序性。然后就变成了线性，可以通过。