PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: apoorv_me, tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
There are N sectors, the i-th has budget A_i.
It’s possible to transfer some budget from one sector, but only if the first sector remains with a budget of at least X after the transfer.
Find the maximum number of sectors that can have a budget of at least X after some transfers.
EXPLANATION:
Let’s call a sector good if A_i \geq X, and bad otherwise.
Each good sector gives us some amount of budget that can be transferred to a bad sector.
Since we aren’t allowed to go below X, we can transfer (A_i - X) to other sectors.
Let S denote the sum of (A_i - X) across all good sectors i.
This extra S can then be distributed to bad sectors to (hopefully) make them reach X themselves.
Clearly, it’s best to first distribute to whichever sectors are already closest to reaching X - that is, it’s optimal to distribute to bad sectors in descending value of their A_i values.
This gives us the following algorithm:
- Compute S as the sum of (A_i - X) across all i such that A_i \geq X.
- Then, consider all i such that A_i \lt X.
Iterate over them in descending order of A_i, and if S \geq X - A_i, set A_i to X and reduce S by (X - A_i).
Iterating over values in descending order is easily done by simply sorting them first.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans, extra = 0, 0
for y in reversed(a):
if y >= x:
ans += 1
extra += y - x
else:
if extra >= x - y:
extra -= x - y
ans += 1
print(ans)