PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array A of length N+1.
You can repeatedly swap A_{N+1} with any other A_i, as long as A_i \leq 2A_{N+1}.
Minimize the sum of the first N elements of A.
EXPLANATION:
Swapping rearranges the elements of A, but doesn’t change the overall set of elements.
Since we care about the sum of the first N elements of A, that means we care about the sum of the entirety of A, minus the last element A_{N+1}.
Our goal is to minimize this quantity, which is equivalent to making A_{N+1} as large as possible.
This can in fact be done greedily.
Repeatedly perform the following process:
- Find any A_i such that A_i \gt A_{N+1} but A_i \leq 2A_{N+1}.
- If no such A_i exists, stop the process immediately.
- Otherwise, A_i \gt A_{N+1}, so it’s beneficial to perform the swap.
The value at index N+1 will increase after this swap, which is good - our aim is to make it as large as possible, after all.
The value at index N+1 keeps increasing, so this process will run at most N times in total.
Each time, we run one loop to find which element to swap with, taking \mathcal{O}(N) time.
So, overall, the complexity is \mathcal{O}(N^2).
It’s possible to improve the complexity to \mathcal{O}(N\log N) by sorting the array first, but this wasn’t necessary to get AC - bruteforce works.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
while True:
mx = -1
for i in range(n):
if a[i] <= 2*a[n]:
if mx == -1 or a[i] > a[mx]: mx = i
if mx == -1 or a[mx] <= a[n]: break
a[mx], a[n] = a[n], a[mx]
print(sum(a[:n]))