Codeforces Round #737 Ezzat and Two Subsequences 题解 (Java/C++)

题解

首先，不难猜到这个题的最终结论：那就是最大的数分为一段，剩下的部分分为另一段。但这个题目的证明还是有点意思的。

首先我们令$a_1\geq a_2 \geq \dots \geq a_n$，再令$x+y=n$。于是，我们需要证明的是$$\frac{a_1+a_2+\dots+a_x}{x}+\frac{a_{x+1}+a_{x+2}+\dots+a_{x+y}}{y} \geq \frac{a_1+a_2+\dots+a_x+a_{x+1}}{x+1}+\frac{a_{x+2}+\dots+a_{x+y}}{y-1}$$

这个不等式的证明看似复杂，但结合$a_1\geq a_2 \geq \dots \geq a_n$后，我们不难想到$\frac{a_1+a_2+\dots+a_x}{x} \geq \frac{a_1+a_2+\dots+a_x+a_{x+1}}{x+1}$且$\frac{a_{x+1}+a_{x+2}+\dots+a_{x+y}}{y} \geq \frac{a_{x+2}+\dots+a_{x+y}}{y-1}$。
因为$a_{x+1}$是前半段中最小的数，却是后半段中最大的数。当我们把$a_{x+1}$从后半段移往前半段时，前后两段的平均值都会下降。

因此，为了获得最大的$f(a)+f(b)$，我们会不断的把前半段的值移往后半段，直到前半段只剩下最大的$a_1$为止。

代码

Java

C++