洛谷 - P1582 - 倒水 - 位运算

佚名 6年前 (2019-04-11) 随笔 888人围观抢沙发百度已收录

https://www.luogu.org/problemnew/show/P1582
要求用最少的瓶子,那肯定不能有两个一样的瓶子,否则合并更优.
枚举其二进制位,每次加上lowbit,将最后一个1加上.

显然最多logn次.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,k;

int main(){
    cin>>n>>k;

    bitset<32> b(n);
    //cout<<b<<endl;

    ll sum=0;
    while(b.count()>k){
        ll cn=n&-n;
        //cout<<bitset<32>(cn)<<endl;
        n+=cn;
        sum+=cn;
        b=bitset<32>(n);
        //cout<<b<<endl;
    }

    //cout<<b<<endl;
    cout<<sum<<endl;
}