题意

高桥去游乐园玩。

有 $n$ 个游乐设施，每次玩时满意度加上此设施的乐趣值，同时设施的乐趣值减一，直到变成 $0$。

一个设施可以玩多次，求一共玩 $k$ 次后高桥满意度的最大值。

$n \leq 1 \times 10^5$；

$k,a_i \leq 2 \times 10^9$。

思路

贪心，高桥一定会选当前乐趣值最大的。

考虑将所有设施的乐趣值从大到小排序一下，形成阶梯分布。

每次把阶梯最高一层（也就是当前乐趣最大值）削掉，如此这样重复下去即可。

---

还可以使用二分。

我们可以二分出分界值 $p$，其满足单调性，$p$ 肯定唯一。

把所有大于 $p$ 的变成 $p$，再把其中一些 $p$ 变成 $p-1$。

两方法均可在 $O(n \log n)$ 时间内跑完。

代码就不给了。