PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Sorting
PROBLEM:
There are N monsters, the i-th has A_i health.
You can either attack all monsters for 1 damage each, after which any monster with 0 health will die; or kill any one monster of your choice regardless of its health.
Find the minimum number of attacks needed to kill all the monsters.
EXPLANATION:
The attack which hits every monster will be called an “AOE attack”.
Suppose we perform X AOE attacks in total.
Then,
- Every monster with health \leq X will definitely be dead just from these, so we don’t need to waste any single target attacks on them.
- Every monster with health \gt X will surely not be dead just from these, so each of them will need one single target attack to finish it off.
So, if there are R_X monsters with health \gt X, the total number of attacks needed is X + R_X.
Our goal is thus to find the minimum value of X + R_X across all possible values of X.
While there are many potential values of X to check for, most of them aren’t really relevant.
Specifically, it can be seen that an optimal X must be one of the elements of A.
This is because, if X is not an element of A, we’ll have R_X = R_{X-1}, and so X-1 + R_{X-1} \lt X + R_X; meaning X certainly wasn’t optimal.
This gives us a fairly simple solution: try each A_i as X, compute R_X, and take the minimum of (X + R_X) across them all.
The only remaining part now is actually computing R_X quickly.
For this, recall that R_X is just “how many elements of A are greater than X?”
To deal with this easily, we can simply sort the array A, so that all such elements will form a suffix; and this suffix can be found using binary search (for example, std::lower_bound in C++).
Alternately, to avoid binary search, after sorting so that A_1 \leq A_2 \leq \ldots \leq A_N, upon fixing A_i = X you can simply take R_X = N - i.
This is not technically correct if there are more elements equal to X after index i; but in any case the true R_X will only be smaller than this value, and we’ll compute the correct value when looking at the rightmost occurrence of X anyway.
So, after sorting, the solution is to simply print the minimum of (A_i + N - i) across all i.
Don’t forget to consider the case when no AOE attacks are used, and the answer is just N.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = n
for i in range(n):
ans = min(ans, a[i] + n-1-i)
print(ans)