See the problem here, https://codeforces.com/contest/1369/problem/C and the (hard to understand proof here, https://codeforces.com/blog/entry/79235
"Lee has n integers a1,a2,…,an in his backpack and he has k friends. Lee would like to distribute all integers in his backpack between his friends, such that the i-th friend will get exactly wi
integers and each integer will be handed over to exactly one friend.
Let's define the happiness of a friend as the sum of the maximum and the minimum integer he'll get.
Lee would like to make his friends as happy as possible, in other words, he'd like to maximize the sum of friends' happiness. Now he asks you to calculate the maximum sum of friends' happiness."
I cannot understand the solution they have given in the blog at all. Could anyone please explain how this proof works and has another way to explain it.
It's a bit more complicated than needed, I would say. Let's try to make it a bit more simple. I assume that you have already figured out the part about the friends with $w_i = 1$ (if not I will edit to explain) so let's just assume that all the friends want two or more items. Now, let's also assume that $a_n \ge a_{n-1} \ge... \ge a_2 \ge a_1$. Since $a_n$ is the max it will be the largest of a friend no matter which one takes it so it will appear in the sum of the final answer. A similar argument applies to $a_1$ as well. So we can give them both to friend $i$. Now the question is about $a_2$. Do we want to give it to a different friend? Not really, because it would be his smallest and we would like to maximize that. So, if we can, we must give to $i$. That is, we would like $i$ to need 3 or more items. Continuing the same way wondering about $a_3$, we end up to the same conclusion: if $i$ can take it then we will give it to him. So we conclude that we would like $w_i$ to be as large as possible, or in other words to be the largest $w$.
Now, that the greedy algorithm is more clear, we can break its proof of optimality into three parts: first prove that $u_i$ must have the $w_i-1$ smallest elements, which the author does via the standard exchange argument, then that $u_i$ has $a_n$ in it, which the author shows via swapping the largest elements of the friends, and then that the friends are ordered based on their $w$s.
I would suggest that you study the greedy algorithm a bit more, then work each of the three proving steps independently and if you have any questions feel free to ask.