648. Spending and Recovering Power
You start with an amount of POWER and a score of 0, and hold a bag of tokens, each with a value. Each token may be played at most once, in one of two ways:
· face up: costs its value in power and gains 1 score. Needs power at least that value. · face down: gains its value in power and costs 1 score. Needs a score of at least 1.
Print the largest score reachable.
tokens 100, power 50 -> 0 cannot afford it and cannot pay a score
tokens 100 200, power 150 -> 1
tokens 100 200 300 400, power 200 -> 2
## The greedy
Sort the tokens. Then:
while i <= j:
if power >= token[i]: play it face up (spend the CHEAPEST)
else if score > 0: play token[j] face down (sell the DEAREST)
else: stop
Track the best score ever reached, not the final one: selling a token lowers the score, and the peak may have come earlier.
## Why cheapest up and dearest down
Gaining a score costs power, so buy the CHEAPEST score available: it leaves the most power for the next purchase, and every score is worth the same 1 point.
Selling costs a score, so get the most power for it: sell the DEAREST token, because one score point buys the most power that way.
Both halves are the same exchange argument. Suppose an optimal play buys some token p while a
cheaper unused token q exists. Swapping them keeps the same score and leaves at least as much
power, so the rest of the plan still works. The selling side is the mirror image.
## Why the peak, not the end
The loop may sell a token and then fail to buy anything, ending with a lower score than it once had. Nothing forces the sequence to end at its maximum, so the maximum has to be remembered.
On 26 66 38 26 29 with power 88 the answer is 3, and a solution reporting the final score
instead of the peak can report less.
## Why stopping is safe
When power is short and the score is 0, neither move is available and no later move can become available, because nothing can increase power without spending a score. So stopping is correct rather than merely convenient.
## Boundaries
Power below every token and no score gives 0. Power above everything buys every token, so the answer is the number of tokens.
## Overflow
Power reaches 10^9 and each face-down play adds a token value, so the running power can reach
about 10^9 + 200000 * 10^9. Use 64 bits.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ power ≤ 10^9` - `1 ≤ each token value ≤ 10^9`
Input
The first line contains two integers n and power.
The second line contains n integers, the token values.
Output
Print one integer, the largest score reachable.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.