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

Solution:

First, it is not difficult to guess the conclusion of this question: that is, the largest number is divided into one subsequence, and the remaining part is divided into another subsequence. But the proof of this problem is still a bit interesting.

First we set $a_1\geq a_2 \geq \dots \geq a_n$, and then set $x+y=n$. So what we need to prove is$$\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}$$

The proof of this inequality seems complicated, but after combining $a_1\geq a_2 \geq \dots \geq a_n$, it is not difficult to find that: $\frac{a_1+a_2+\dots+a_x}{x} \geq \frac{a_1+a_2+\dots+a_x+a_{x+1}}{x+1}$ and $\frac{a_{x+1}+a_{x+2}+\dots+a_{x+y}}{y} \geq \frac{a_{x+2}+\dots+a_{x+y}}{y-1}$ are always established.
Because $a_{x+1}$ is the smallest number in the first part, but it is the largest number in the second part. When we move $a_{x+1}$ from the second part to the first part, the average value of both two parts will decrease.

Therefore, to obtain the largest $f(a)+f(b)$, we will continue to move the value of the first part to the second part until only the largest $a_1$ is left in the first part.

Code:

Java

C++