编程题倒水1.倒水题目描述一天,天天买了N个容量可以认为是无限大的瓶子,初始时每个瓶子里有1升水.天天发现瓶子实在太多了,于是他决定保留不超过K个瓶子.每次他选择两个当前

Question

编程题 倒水
1.倒水
【题目描述】
一天,天天买了 N 个容量可以认为是无限大的瓶子,初始时每个瓶子里有
1升水.天天发现瓶子实在太多了,于是他决定保留不超过K个瓶子.每次他选
择两个当前含水量相同的瓶子合并,把一个瓶子的水全部倒进另一个瓶,然后把
空瓶丢弃（不能丢弃有水的瓶子）.
显然在某些情况下天天无法达到目标,比如N=3,K=1.此时天天会重新买
一些新的瓶子（新瓶子的容量无限,开始时有1升水）,以达到目标.
现在天天想知道,最少需要买多少新瓶子才能达到目标?
【输入文件】
一行两个正整数N,K（1

Answer 1

用位操作最为方便.首先问题核心思想是,每2^n个瓶子可以最终合并保留1个瓶子（一颗满二叉树）,本题就变为N能写成最少多少项2的n次方的和的形式,有多少项就会最终剩多少瓶,要添加的瓶子数量就是要减少之前多项式的项数.比如198 = 128+64+4+2,尽可能合并后最终会剩4瓶.若最后需要保留3瓶,则只需加2,变成128+64+8.
用位操作,198二进制为1100 0110,里面有4个1.要保留3瓶,就是要找出一个含有3个1的二进制数,这个数应该是最小的大于198的数,即1100 1000.我们可以看出问题可以简化为从高往低第k位需要多少来进位：0110需要多少才能变成1000
代码：
public int compute2s(int num,int k){
int moved = 0;
int ones = 0;
while(ones < k){
if((num&0x40000000)!=0){
ones++;
if(ones == k)
break;
num -= 0x40000000;
}
num moved;
int upBond = 1;
while(upBond