题解：CF2118C Make It Beautiful

· · 题解

本次 C 有点低于之前 Div.2 的难度。

题目大意

给你一堆数，定义每个数的美丽度为二进制下 1 的个数。再给你常数 k ，可以重复至多 k 次，每次给某数加一，求最后最大的美丽度之和。

分析

先思考用多少代价能把一个数的美丽度增加。先把这个数拆位，贪心地考虑，美丽值加 1 当然是把其中最低的 0 变成 1 ，贡献当然是这一位的大小。加 2 就是在此基础上在加 1 ，以此类推。

既然每次都只能耗确定的贡献加一，那能不能考虑贪心？第一次先找到其中美丽度加一的代价最小的，加一，再更新这个数的消耗。然后再选最小的，再消耗，直到 k 不够用了，结束。

实现

用优先队列实现，先把数字和贡献存入，找到最小的，更新，再放回去。因为每次贡献成倍增长，所以每个数最多更新 O(\log m) 次，共有 n 个数，因为用的是堆，所以每次更新还有 O(\log n) 的代价，所以最终时间复杂度为 O(n \log n \log m)，能过。

code:codeforces.com/contest/2118/submission/324087206