PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have N glasses of water.
In one move, you can move all the water from one glass to another.
This must be done exactly K times.
Maximize the maximum amount of water in any glass in the end.
EXPLANATION:
Each operation allows us to combine the water in two glasses.
So, K operations allows us to combine the water in upto K+1 glasses into a single glass.
We’re aiming to maximize the maximum amount, so it’s optimal to just choose the most voluminous K+1 glasses to combine.
Thus, the answer is simply the sum of values of the largest K+1 glasses.
This can be computed in \mathcal{O}(NK) time by repeatedly finding and discarding the maximum element; or in \mathcal{O}(N\log N) by sorting and looking at the last K+1 elements.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
print(sum(a[:min(n, k+1)]))