题解 P1582 【倒水】

pantw · 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);
}