Maximum Median

Core idea

Sort the array. Let

$$m = \left\lfloor \frac n2 \right\rfloor$$

be the median index in $0$-based indexing. Initially the median is $a_m$.

We want to maximize the median using only increments. The tempting wrong move is to randomly pump numbers in the left half. Don't. That's usually burning operations for no reason.

Checking if a median value is possible

Suppose we ask a simpler question:

Can we make the median at least $x$ using at most $k$ operations?

For an odd-sized array, median $\ge x$ means at least $(n+1)/2$ elements are $\ge x$.

After sorting, the best candidates for these $(n+1)/2$ elements are the largest $(n+1)/2$ elements:

$$a_m, a_{m+1}, \dots, a_{n-1}.$$

Why? Because increasing a larger number to $x$ is never more expensive than increasing a smaller number to $x$. If you choose some element from the left half instead of one from this suffix, you're choosing the worse deal. Classic competitive programming coupon logic: take the discount, don't be a hero.

So the minimum number of operations needed to make the median at least $x$ is

$$\text{cost}(x) = \sum_{i=m}^{n-1} \max(0, x-a_i).$$

If $\text{cost}(x) \le k$, then $x$ is feasible.

Monotonicity

If we can make the median at least $x$, then we can definitely make it at least any smaller value $y \le x$.

So feasibility is monotonic:

$$\text{feasible}(x) = \bigl(\text{cost}(x) \le k\bigr).$$

This screams binary search. Loudly. With a megaphone.

The answer is at least $a_m$, and it can never exceed $a_m+k$, because raising the median by more than $k$ would require more than $k$ total increments already for the median candidate alone.

So binary search on:

$$[a_m,\ a_m+k].$$

Complexity

Sorting costs:

$$O(n \log n).$$

Each feasibility check scans the suffix, costing $O(n)$, and binary search needs about $31$ iterations because values are up to around $2\cdot 10^9$.

Total complexity:

$$O(n \log n + n \log k),$$

which is easily fine for $n \le 2\cdot 10^5$.

Memory usage is:

$$O(n).$$