ABC216E 题解

## 题意 高桥去游乐园玩。 有 $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)$ 时间内跑完。 代码就不给了。