题解：P14462 【MX-S10-T3】『FeOI-4』寻宝游戏

考虑以下策略：

1. 选择一个位置作为基准，将所有的泡面移到这里。

令最大的位置为 $mx$，严格次大的位置为 $se$（即 $a_{se}<a_{mx}$）。

容易发现基准一定是 $se$ 或 $mx$（因为奇偶性可能不对）。两个都试一下即可。

特别地，当所有 $a_i=1$ 时，有可能使用 $n+1$ 作为基准。

2. 将所有泡面移入位置 $k$。

令剩下最多有 $x$，剩余的和为 $S$。若奇偶性不对需要先从基准和 $x$ 中拿出一个放入 $n+1$。

• 若 $x\le S$，直接全移过去即可。具体来说，每次选择最多的两个位置，各拿出一个放入 $k$。操作次数为 $(x+S)/2$。
• 若 $x> S$，可以这样：从 $S$ 中和 $x$ 中拿出一个，放入 $n+1$，直到合法。操作次数为 $x$。

发现操作次数为 $\max((S+x)/2,x)$。

容易发现这个策略在 $n\ge 3$ 时是对的。

考虑特判 $n=1,n=2$ 的情况。

考虑 $n=2$ 的情况。令他们为 $x,y(x\le y)$。

• 当 $x,y$ 比较大的时候，答案为 $x$。
• 当 $y$ 比较大的时候，答案只与 $x$ 有关。

剩下的情况可以 打表/手玩 求出来。

具体来说，我们只需要玩出 $x,y\le 6$ 和 $x\le 6,y> 6$ 的情况即可。