822. The Longest Run You Can Bring Level
A workshop holds n components, component i currently at grade a[i]. One unit of work
raises one component by exactly one grade. At most k units of work are available.
Print the largest number of components that can be made to share a single grade.
grades 1 2 4 4, k = 5 -> 4 raise 1 to 4 and 2 to 4, cost 3 + 2 = 5
grades 1 4 8 13, k = 8 -> 2 raise 4 to 8, cost 4
grades 7 7 3 7 7, k = 0 -> 4 the four sevens are already equal
## Sort first, and then notice what is being searched
Work only ever RAISES a grade, so the components brought up to a common grade g must all
start at or below g, and it is never worse to choose the ones closest to g. Sort the
grades; the chosen set is then a contiguous RUN of the sorted list, and the target is the
largest grade in that run.
The cost of levelling the run a[r-L+1 .. r] up to a[r] is
cost = a[r] * L - (a[r-L+1] + ... + a[r])
which a prefix-sum table answers in constant time once the sort is done.
What is being binary searched here is not a grade and not a cost. It is the LENGTH of the run. That is worth saying out loud, because the instinct after the earlier problems in this block is to search the answer's units, and the answer's units here are a count of components.
## Why the predicate is monotone in the length
Suppose a run of length L ending at r is affordable. Drop its smallest element. The
remaining run has length L - 1, still ends at r, and its cost is
cost(L - 1) = cost(L) - (a[r] - a[r-L+1])
which is not larger, because the list is sorted so a[r] >= a[r-L+1]. So if some run of length
L fits the budget, some run of length L-1 does too, and the affordable lengths form a
prefix 1, 2, ..., answer.
Length 1 is always affordable at zero cost, so the answer exists and is at least 1.
## The check
ok(L): for every r from L-1 to n-1
if a[r] * L - (pre[r+1] - pre[r+1-L]) <= k return true
return false
One pass, O(n), and the whole solution is O(n log n) for the sort plus O(n log n) for
the search.
Sliding a window is an alternative that answers the same question in one pass without any binary search at all. It is a fine solution and worth knowing. This problem asks for the search because the window version hides what the predicate is, and the predicate is the transferable part.
## The loop shape
The affordable lengths form a prefix, so this searches for the LAST true, exactly as the tent problem 821 does:
lo = 1, hi = n
mid = hi - (hi - lo) / 2
ok(mid) ? lo = mid : hi = mid - 1
and the upward midpoint is again what stops lo = hi - 1 from looping forever.
## Overflow
a[r] * L reaches 10^9 * 10^5 = 10^14 and the prefix sums reach the same, while k itself
can be 10^14. All three need 64 bits. A 32-bit product here wraps negative, the comparison
against k succeeds, and the answer comes back as n on inputs where it should be 2.
## Cost
Time O(n log n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ k ≤ 100000000000000` - `1 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k, the number of components and the units of work available.
The second line contains n integers a[0] ... a[n-1], the current grades, in any order.
Output
Print one integer, the largest number of components that can be brought to a single common grade within the budget. Print it alone on one line, with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.