PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: ddpigeon,, kiwi26
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
Sorting
PROBLEM:
There are N monsters, the i-th with a health of H_i.
Every day, you can attack one monster and kill it, but only if your attack stat is not smaller than the monster’s health.
At the end of each day, all alive monsters’ health will increase by X.
Find the minimum attack power you need such that there exists a way to kill all the monsters.
EXPLANATION:
Since the health of monsters keeps increasing, leaving high-health monsters alive doesn’t seem like a good idea since their health is only going to increase in the future.
So, intuitively, on each day we must try to kill the monster with highest remaining health.
Let’s arrange the monsters in descending order of their health, i.e. assume H_1 \geq H_2 \geq\ldots\geq H_N.
Suppose our attack power is A. Then,
- On the first day, the highest health is H_1, so we need A \geq H_1 to hold.
- On the second day, all other monsters have increased their health by X.
So, the highest health is H_2 + X; meaning we need A \geq H_2 + X to be able to kill it. - Similarly, on the third day we need A \geq H_3 + 2X, on the fourth day we need A \geq A_4 + 3X, and so on.
In general, on the i-th day, we require A \geq H_i + (i-1)\cdot X to hold.
This gives us a set of lower bounds on A, the attack power required.
Simply taking the maximum of these lower bounds gives us the minimum necessary attack stat, i.e. after sorting H in descending order, the answer is
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, x = map(int, input().split())
h = list(map(int, input().split()))
h = sorted(h)[::-1]
ans = 0
for i in range(n):
ans = max(ans, h[i] + i*x)
ans = max(h[0], h[-1]+(n-1)*x)
print(ans)