Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

ABC216E 题解

posted on 2022-10-23 15:28:18 | under 题解 |

题意

高桥去游乐园玩。

有 $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)$ 时间内跑完。

代码就不给了。