链接在此
就是一道思维题,通过分析题得知,每个瓶子可以装2^x这么多水,即这么多的水可以装在一个瓶子里,所以:
每2^x个瓶子可以合成一个瓶子。
以样例13 5来说,
13=8+4+1.
也就是说13个瓶子可以合并成3个瓶子，但此时不满足“小于k个”条件，所以需要购买瓶子。
买1个，14=8+4+2，没有什么卵用。(只能装在三个瓶子)
买2个，15=8+4+2+1，好像更糟。（只能装在四个瓶子里了）
买3个，16=16,搞定。（只用一个瓶子了,满足需求）
根据上述过程可以得出初步思路：算出n可以分成几个2^x相加，也就是可以合成几个瓶子。如果结果>k那么买一个空瓶重复上述过程。
所以一想到2^x的次方,肯定想到2进制计算,所以要看输入的n的二进制中有多少个1,然后不符按累加,知道满足需求,如果单纯用普通方法肯定会T,所以所有的操作都要用位运算,才能提高运算效率!!!具体看代码
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
int cal(ll x) // 算x的二进制表示中有多少个1.
{
int ans=0;
while(x){
x &= (x-1); //这个就是精辟, 这样可以把x中最右边那个1变为0.
ans ++;
}
return ans;
}
int main()
{
int t;
cin >> t;
while(t--){
ll n,k;
cin >> n >> k ;
if(n<=k){
printf("0\n");
continue;
}
int sum=0;
int m=n;
int i;
while(cal(n) > k ){
for(i=1;;i <<= 1){ //i的累加也要用二进制,这样才快,因为我们是对n进行二进制进位,所以就是进2的次方 , 只要是位上面是 1 就进位来看. 如果是0 就不用管,这样进位就快的多.!
if(n&i)
break;
}
n+=i;
}
cout << n-m <<endl;
}
}
