P1582 倒水（贪心 + lowbbit)

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 = ;

    for(;x;x -= x & -x){

        c++;

    }

    return c;

}

int ans;

signed main(){

    ios::sync_with_stdio();

    cin >> n >> k;

    while(check(n) > k){

        ans += n & -n;

        n += n & -n;

    }

    cout << ans;

    return ;

}

如果要是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

巴特西

P1582 倒水（贪心 + lowbbit)

最新文章

热门文章