693. The Longest Run You Can Level Up
You may add 1 to any value, and you may do this at most k times in total. Afterwards, count
how many values are EQUAL to the most common value, and make that count as large as possible.
Print that count.
1 2 4, k = 5 -> 3 raise 1 by 3 and 2 by 2, giving 4 4 4
1 4 8 13, k = 5 -> 2
3 9 6, k = 2 -> 1
## Sorting is allowed, and it is the whole opening
The values chosen to become equal need not be adjacent in the input, and the cost of raising a set of values to a common target does not depend on their order.
So sort. Now the chosen values ARE contiguous: if you are raising some set to a target, adding any value between the smallest and largest of that set costs less than the ones already included, so including it is never worse.
That is what turns a subset problem into a window problem, and it is the step worth recognising. The same move opened problem 660.
## Raise everything to the window maximum
After sorting, a window lo .. hi is raised to a[hi], the largest inside it. The cost is
a[hi] * (hi - lo + 1) - (sum of the window)
which is "what the window would total if every value were already the maximum" minus what it actually totals.
Raising to anything HIGHER than a[hi] costs strictly more and gains nothing, so the maximum
is always the right target.
## The sweep
for hi in 0 .. n-1:
total += a[hi]
while a[hi] * (hi - lo + 1) - total > k:
total -= a[lo]; lo += 1
best = max(best, hi - lo + 1)
## Why the left edge never returns
Moving hi right can only raise the target and therefore the cost, so the window may become
too expensive and must shrink. Shrinking from the left removes the cheapest-to-raise value and
always reduces the cost, so it never has to be undone.
## Overflow
a[hi] * (hi - lo + 1) reaches 10^9 times 2 * 10^5, which is 2 * 10^14. The cost
expression needs 64 bits, and so does the running total.
That product is the part people leave in 32 bits, because each factor looks small on its own.
## Boundaries
k = 0 gives the largest number of values that are ALREADY equal. A single value answers 1.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 10^14` - `1 ≤ each value ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the largest achievable count of equal values.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.