洛谷P1582 倒水题解

题目

分析

这个题并不难，只是需要仔细思考
我们首先可以很轻松的把这个题给疏通一下题意。

1：首先我们最后每个瓶子中装的水一定是一个$2^x$，因为每次都是$2$倍的加，这个应该很好理解。

2：我们要明白$n$转换成二进制后，所含$1$的个数是什么意思，可以从二进制的定义里面找，个数即是每个数如果分成多个二进制数的话，所需的二进制数的个数。

3：其次我们明白这剩下的$k$个瓶子代表什么意思,它代表着当前的水量(即$n$)转变成二进制后该数的1的数目一定要$<=k$

为什么呢，我们想一下，如果该数目大于$k$则$k$个瓶子一定装不满，因此我们一定要多要几个瓶子啊，可是这些瓶子只能从一开始加上且一开始的水量为$1$，所以我们可以求出一开始的水量，和最小的（满足1的个数$<=k$）且（$该数>=n$）的一个数然后算出它们的差值就是一开始我们要加上的瓶子。

#include <cstdio>

int n, k, ans;

int main()

{

    scanf("%d%d", &n, &k);

    int a = n;

    while(__builtin_popcount(n) > k) n += n & -n;

    printf("%d", n - a);

}