前言：本帖出发点并非讨论区题解，只是因为题解区无线性做法，故在此分享。

首先排序是需要的，但我们选择桶排。

我们枚举 $i$，设此时答案 $x$ 满足 $a_{i} \le x \le a_{i+1}$，则根据题意，大于 $x$ 的部分提供的多余量为 $(\sum_{j=1}^i-i \times x) \times k$，小于 $x$ 的部分所需要的量为 $(n-i) \times x-\sum_{j=i+1}^n$，这两个式子需要相等，我们解这个 $x$。若 $x$ 符合 $a_{i} \le x \le a_{i+1}$ 则是合法解。