PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author, Tester, and Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting
PROBLEM:
K people line up to buy N pastries from a shop. You’re L-th in line.
The pastries have deliciousness values A_1, A_2, \ldots, A_N.
On their turn, a person will always pick the most delicious remaining pastry; then move to the back of the line.
Find the total deliciousness of pastries you buy.
EXPLANATION:
Let’s sort the array A, so that A_1 \geq A_2 \geq \ldots \geq A_N.
Then, notice that:
- The first person will choose A_1
- The second person will choose A_2
- The third person will choose A_3
\vdots - The K-th person will choose A_K
- Then, it’s the first person’s turn again, who will pick A_{K+1}
- The second person gets another turn, and picks A_{K+2}
\vdots
In general, the i-th person in line will pick A_i, A_{i+K}, A_{i+2K}, \ldots.
You’re L-th in line, so you’ll pick A_L, A_{L+K}, A_{L+2K}, \ldots
Simply print the sum of these numbers.
Since N can be as large as 2\cdot 10^5 in this task, sorting A needs to be done in \mathcal{O}(N\log N) using an efficient algorithm, such as mergesort or quicksort; \mathcal{O}(N^2) sort algorithms such as bubble sort and insertion sort won’t be fast enough.
The simplest way is to just use your language’s built-in sort function.
TIME COMPLEXITY
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, k, l = map(int, input().split())
a = sorted(list(map(int, input().split())))[::-1]
print(sum(a[l-1::k]))