最后剩下的数 2

答案为 $\min(A_1,\ldots,A_N)+N-1$。

设某次操作前的最小值为 $m$，移除的值为 $x$。任意剩余的值 $y$ 分为两种情况。

• 若 $y\le x$，则变成 $y+1\ge m+1$。
• 若 $y>x$，则保持不变。由于值均为整数且 ，有 。

因此最小值每次至少增加1。总共进行恰好 $N-1$ 次操作，故最终值至少为初始最小值加 $N-1$。

要达到这个下界，每次移除当前最大值即可。剩余的所有值都不大于被移除的值，因此都增加1。至少有一个最小值会留下：若移除最大值同时也移除了一个最小值，则当前所有值都相等，还会有其他最小值留下。因此每次最小值恰好增加1，达到下界。

$N=1$ 时不进行操作，公式仍然成立。唯一子任务的预期解法是在读入时仅维护最小值。时间复杂度为 $O(N)$，额外空间为 $O(1)$。

朴素解法每次找到并移除最大值，再逐一更新剩余值。结果正确，但时间复杂度为 $O(N^2)$，空间复杂度为 $O(N)$，最大输入下会超时。

每个整数至多增加 $N-1$ 次，所以答案以及模拟过程中的值都不超过 $10^9+200\,000-1=1\,000\,199\,999$。所有整数计算均在有符号64位范围内。

Solution written by GPT6