题目链接:https://www.luogu.org/problemnew/show/P1582
因为需要两两合并,所以瓶子里的水的值只能有2^n,所以可以联想到二进制,然后我们可以推几个数,发现最后所得的瓶子数就等于n的二进制数的1的个数,所以我们可以一个一个加n的值,然后判断是不是小于k的就行了(有的人说会T,我是100AC了),然而这种方法略显暴力了点,所以我们可以再想一下,对于一个数的二进制数,我们在它的二进制数的最低位的1加上1的话,所得的数的二进制的1的个数是不会增加的,比如101+1=110,但是如果是110+1=111这样就相当于多了1,所以我们可以利用这一点来对code来进一步优化,用lowbit函数找到最低位的1的位置,再更新n的值就好了,code中的__builtin_popcount()函数是用来求当前数的二进制数中的1的个数的,详细的可以看这篇博客:__builtin_函数。
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int num = 0;
while(__builtin_popcount(n) > k){
num++;
n++;
}
cout<<num<<endl;
return 0;
}
AC代码(lowbit优化):
#include <bits/stdc++.h>
using namespace std;
int lowbit(int x){return x & (-x);}
int main()
{
int n,k;
cin>>n>>k;
int num = 0;
while(__builtin_popcount(n) > k){
num += lowbit(n);
n += lowbit(n);
}
cout<<num<<endl;
return 0;
}