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

Submission #125492886 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #125493691 - Codeforces
Codeforces. Programming competitions and contests, programming community