自动搬运

查看原文

来自洛谷，原作者为

	pantw **

搬运于2025-08-24 21:26:44，当前版本为作者最后更新于2018-01-05 22:24:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

纯二进制题目。

因为所有的水都是由两份相同的水合并而成的，因此每瓶水的体积一定是$2^i,(i\in N)$升。

最后保留k个瓶子，那么最后总的升数的二进制表示中，1的个数一定<=k。

那么我们只要贪心地往n上加上lowbit(n)即可。

这个lowbit就是树状数组那个lowbit啦

简化代码的trick：

使用内置函数\_\_builtin\_popcount()来计算一个数的二进制表示中1的数量。

这样下来，代码简化到仅剩7行。

惊不惊喜，意不意外？

那么问题来了，为什么这题是 提高+/省选- 呐？

#include <cstdio>
int n, k, ans;
int main() {
    scanf("%d%d", &n, &k);
    while(__builtin_popcount(n) > k) ans += n & -n, n += n & -n;
    printf("%d", ans);
}