題目鏈接：http://www.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747最終的水要放在K個(gè)瓶子里面，而每個(gè)瓶子中的水的數(shù)量必須為2的整數(shù)冪，即最終的水?dāng)?shù)量n'要能分解成
k個(gè)2的整數(shù)冪，也就是new_n的二進(jìn)制表示中1的個(gè)數(shù)要<=k.
用count(n)表示n的二進(jìn)制表示中1的個(gè)數(shù)，如果count(n)<=k，那就不需要買瓶子了。
如果count(n)>k，說明我們要找到第一個(gè)n'使得n'>n并且count(n')<=k。那就是說我們要減少n中1的個(gè)數(shù)。
我們把n表示為x0ab.其中a為全1,b為全0. a,b的長(zhǎng)度>=0.
很明顯，第一個(gè)減少1的個(gè)數(shù)的n'應(yīng)該為x1{(a+b)個(gè)0}，也就是把a(bǔ)b全部變成0.ab前的0變?yōu)?.即加上一個(gè)1<<length(b).
因?yàn)閷?duì)b來說，無論增加多少都會(huì)增加1的個(gè)數(shù)。
然后再判斷n'的1的個(gè)數(shù)，直到count(n)<=k。
因?yàn)閚最大為10^7，n'最大為10^8，int類型不會(huì)溢出。因此邊界條件就無需判斷了。
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 //找到第一個(gè)1...第n次犯了沒把N&mask括號(hào)括起來的錯(cuò)誤了。。。&的優(yōu)先級(jí)<等號(hào)...
30 while( (N&mask)==0) mask<<=1;
31 //加上mask使得1的數(shù)目減少
32 N+=mask;
33 res += mask;
34 }
35
36 return res;
37 }
38
39