題目鏈接：http://www.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747最終的水要放在K個瓶子里面，而每個瓶子中的水的數量必須為2的整數冪，即最終的水數量n'要能分解成
k個2的整數冪，也就是new_n的二進制表示中1的個數要<=k.
用count(n)表示n的二進制表示中1的個數，如果count(n)<=k，那就不需要買瓶子了。
如果count(n)>k，說明我們要找到第一個n'使得n'>n并且count(n')<=k。那就是說我們要減少n中1的個數。
我們把n表示為x0ab.其中a為全1,b為全0. a,b的長度>=0.
很明顯，第一個減少1的個數的n'應該為x1{(a+b)個0}，也就是把ab全部變成0.ab前的0變為1.即加上一個1<<length(b).
因為對b來說，無論增加多少都會增加1的個數。
然后再判斷n'的1的個數，直到count(n)<=k。
因為n最大為10^7，n'最大為10^8，int類型不會溢出。因此邊界條件就無需判斷了。
1 #include <vector>
2 #include <algorithm>
3 #include <sstream>
4 #include <string>
5 #include <iostream>
6
7 using namespace std;
8
9 int count(int i)
10 {
11 int res = 0;
12 while(i!=0){
13 i&=(i-1);
14 res++;
15 }
16
17 return res;
18 }
19
20 class PouringWater
21 {
22 public:
23 int getMinBottles(int N, int K)
24 {
25 int res = 0;
26 int mask = 1;
27
28 while(count(N)>K){
29 //找到第一個1...第n次犯了沒把N&mask括號括起來的錯誤了。。。&的優先級<等號...
30 while( (N&mask)==0) mask<<=1;
31 //加上mask使得1的數目減少
32 N+=mask;
33 res += mask;
34 }
35
36 return res;
37 }
38
39