题目描述：

ACX在××信竞组学会信息竞赛，但是他的同学都很巨，于是要他去买水，结果来到某个买水的商店（奇奇怪怪的商店）。

一天,ACX买了 N 个容量可以认为是无限大的瓶子,初始时每个瓶子里有 1 升水。

ACX发现瓶子实在太多了,于是他决定 保留不超过 K 个瓶子。每次他选择两个当前含水量相同的瓶子合并,把一个瓶子的水全部倒进另一个瓶,然后把空瓶丢弃(不能丢弃有水的瓶子)。

显然在某些情况下ACX无法达到目标,比如 N=3,K=1.此时ACX会重新买一些新的瓶子(新瓶子容量无限,开始时有 1 升水),以达到目标。现

在ACX想知道,最少需要买多少新瓶子才能达到目标呢?

读入格式：

一行 两个正整数 N,K(1<=N<=10^9 ,K<=1000)

输出格式：

一个非负整数,表示最少需要买多少新瓶子。

样例输入：

3 1

样例输出：

1

 

Solution：

将瓶子中水的体积转换成二进制，如1升可写成0000001，同理两升就是0000010。

题目合并的一定是相同的体积合并，所以容积一定是二的次方倍，这时候我们可以发现，二进制数上的1就可以是一个瓶子，这时候我们就可以将题目转换成加数（数就是多加了几瓶水），如样例：11 加一变成 100 就只有一个瓶子了。

所以题目就可以变成每次加x，使这个数二进制时位上的1的个数小于k

为了方便我们每次就加上最后一位上表示的二进制数如10010（2）时，就加10（2），使最后位置上的1进位从而减少1的个数。

这个题目需要感性理解下吧，理解代码了还是不难的。就是一道套路题～

 

Code：

1 //It is coded by Ning_Mew on 11.1 :) 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 using namespace std; 9 int n,k;10 int need=0;11 int a[10000+10];12 int num(int s){13 int numb=0;14 while(s){numb++;s=s-(s&(-s));}15 return numb;16 }17 int main(){18 freopen("water.in","r",stdin);19 freopen("water.out","w",stdout);20 scanf("%d%d",&n,&k);21 while(num(n)>k){22 need+=(n&(-n));23 n+=(n&(-n));24 }25 printf("%d\n",need);26 return 0;27 }