问题D:杯子(运用了二进制)
程序员文章站
2022-05-08 23:09:50
...
刚开始觉得用BFS可以凑出来(超时预定),也可能我没有剪枝的问题,二进制玩的溜都是大佬啊
总结一下这个题思路
就是先找出一个不小于n的2的幂次,然后除去k位1(二进制),也就是右移k位个1
判断除去k位1后的n是否为0
为0说明杯子数量刚好不用买输出0
如果不为0就还是凑一个不小于此时的n,减去n,就是凑一次的个数
#include<bits/stdc++.h>
using namespace std;
long long n,k;
int main()
{
scanf("%lld %lld",&n,&k);
long long p=1;
while(p*2<n)
{
p*=2;
}
while(n)
{
if(n/p==1)
k--;
if(k==0)
break;
n=n%p;
p>>=1;
}
if(n==0)
{
printf("0\n");
return 0;
}
p=1;
while(p<n)
{
p*=2;
}
printf("%lld\n",p-n);
return 0;
}
推荐阅读