[Luogu T365450] 粉兔杯初赛

有 $n$ 种兔子，每种兔子有 $a_i$ 只。给兔子两两配对（可能有一只兔子轮空），最大化两只兔子种类不同的兔子对数量。$n \le 10^6, a_i \le 10^9$。

样例：

3
4 3 3

答案为 5，可以 1-2, 1-2, 1-3, 1-3, 2-3 这样配成五对。

提示：”每次找出最大的一堆和次大的一堆，然后把次大的直接和最大的全部配对。”这个策略是错解。样例即为反例。

解法

令 $s = \sum\limits_{i=1}^n a_i$，$m = \max\limits_{i=1}^n a_i$。结论：答案为 $\min\left(\left\lfloor\dfrac s 2\right\rfloor, s-m \right)$。

显然 $m > \left\lfloor\dfrac s 2\right\rfloor$ 时，答案为 $s - m$。

考虑 $m \le \left\lfloor\dfrac s 2\right\rfloor$：显然答案上界就是 $\left\lfloor\dfrac s 2\right\rfloor$。接下来证明这个上界必然能取到。

配对策略：每次找出最大的一堆和次大的一堆，分别取出一只配对，其余放回。（P2902 [USACO08MAR] Pearl Pairing G）

直接数学归纳法就可证出结论：

单次操作可以保证”最大值不超过所有数和的一半”这个性质。归纳下去，直到只剩 $2$ 种兔子，再直到较少的兔子仅剩 $1$ 只。

此时多的那种兔子的数量只可能是 $1$ 或 $2$，而这两种都满足结论。