P1582 倒水（贪心 + lowbit)

https://www.luogu.com.cn/problem/P1582

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
//取出1的个数
int check(int x){
    int c = 0;
    for(;x;x -= x & -x){
        c++;
    }
    return c;
}
int ans;
signed main(){
    ios::sync_with_stdio(0);
    cin >> n >> k;
    while(check(n) > k){
        ans += n & -n;
        n += n & -n;
    }
    cout << ans;
    return 0;
}

 如果要是K= 1的 时候，我们很自然的能想到当能满足2ⁿ

的时候是符合题意的，可是数据范围这么大，求2ⁿ

^{显然是不可能的}

这时候怎么办？

二进制呢

5	101	1	2
n	二进制下	lowbit()	合并后瓶子的个数
1	1	1	1
2	10	10	1
3	11	1	1
4	100	100	1

我们可以发现，合并后瓶子个数就是二进制中1的个数 ，我们可以借助lowbit()求出1的个数

然后和k比较，如果相等 说明不用

大于 说明瓶子数量不够 我们要加瓶子，那么也应该从最低为加

小于说明不用加了，输出0