一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)
显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限，开始时有1升水)，以到达目标。
现在CC想知道，最少需要买多少新瓶子才能达到目标呢？
第一行一个整数T，表示有T组数据。
接着T行，每行两个正整数， N,K(1<=N<=10^9，K<=1000)。
一个非负整数，表示最少需要买多少新瓶子。
解题思路：对于 n 瓶一升的水，把他们合并后最少的瓶子数为 n 的二进制中 1 的个数。假设 n 的二进制中 1 的个数大于 k，那么我们要找到 1 个大于 n 的数，且二进制中 1 的个数等于k的最小的数 m，那么答案为 m-n。假设 n 二进制中，最右边的 1 在第 i 位（这里的第几位是从右往左数的，最右边为第 0位），如果加上一个2^i，则结果二进制中 1 的个数必定不会增加。所以只需要一直加上一个 2^i，直到结果中 1 的个数等于 k 即可
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <functional> #include <climits> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int get(LL x) { int sum=0; while(x) { if(x&1) sum++; x>>=1; } return sum; } int main() { int k; LL n,ans; int t; scanf("%d",&t); while(t--) { scanf("%lld%d",&n,&k); ans=0; while(get(n)>k) { LL i; for(i=1;;i<<=1) if(n&i) break; ans+=i; n+=i; } printf("%lld\n",ans); } return 0; }
