编程题倒水1.倒水【题目描述】一天,天天买了N个容量可以认为-查字典问答网

来自骆轶姝的问题

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

　　编程题倒水

　　1.倒水

　　【题目描述】

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

　　1升水.天天发现瓶子实在太多了,于是他决定保留不超过K个瓶子.每次他选

　　择两个当前含水量相同的瓶子合并,把一个瓶子的水全部倒进另一个瓶,然后把

　　空瓶丢弃（不能丢弃有水的瓶子）.

　　显然在某些情况下天天无法达到目标,比如N=3,K=1.此时天天会重新买

　　一些新的瓶子（新瓶子的容量无限,开始时有1升水）,以达到目标.

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

　　【输入文件】

　　一行两个正整数N,K（1

1回答

2020-12-2615:16

我要回答

提示：回答问题需要登录哦！

提交

蔡海鹏

　　用位操作最为方便.首先问题核心思想是,每2^n个瓶子可以最终合并保留1个瓶子（一颗满二叉树）,本题就变为N能写成最少多少项2的n次方的和的形式,有多少项就会最终剩多少瓶,要添加的瓶子数量就是要减少之前多项式的项数.比如198=128+64+4+2,尽可能合并后最终会剩4瓶.若最后需要保留3瓶,则只需加2,变成128+64+8.

　　用位操作,198二进制为11000110,里面有4个1.要保留3瓶,就是要找出一个含有3个1的二进制数,这个数应该是最小的大于198的数,即11001000.我们可以看出问题可以简化为从高往低第k位需要多少来进位：0110需要多少才能变成1000

　　代码：

　　publicintcompute2s(intnum,intk){

　　intmoved=0;

　　intones=0;

　　while(ones