[數學方法]NOIP模擬題：倒水 water 解題報告

【題目描述】

一天， CC 買了 N 個容量可以認為是無限大的瓶子，開始時每個瓶子裡有 1 升水。接著 CC

發現瓶子實在太多了，於是他決定保留不超過 K 個瓶子。每次他選擇兩個當前含水量相同的瓶子，把一個瓶子的水全部倒進另一個裡，然後把空瓶丟棄。（不能丟棄有水的瓶子）

顯然在某些情況下 CC 無法達到目標，比如 N=3,K=1 。此時 CC 會重新買一些新的瓶子（新瓶子容量無限，開始時有 1 升水），以達到目標。

現在 CC 想知道，最少需要買多少新瓶子才能達到目標呢？

輸入文件（ water.in ）：

一行兩個正整數， N,K （ 1<=N<=10^9,K<=1000 ）。

輸出文件（ water.out ）：

一個非負整數，表示最少需要買多少新瓶子。

輸入樣例 1 ：

3 1

輸出樣例 1 ：

1

輸入樣例 2 ：

13 2

輸出樣例 2 ：

3

輸入樣例 3:

1000000 5

輸出樣例 3 ：

15808

樣例說明：

無

資料規模

對於 50% 的資料， N<=10^7

對於 100% 的資料如題目。

【分析】

找一下規律吧，然後數學歸納一下就可以了。
先看一下K=1時的情況：

設再買X個瓶子才能滿足要求。

1. 若N=1，不需要合併，則X=2^0-1=0

2.若N=2
1  1
  2
不需要合併，則X=2^1-2=0

3.若N=3
1 1 1
  2 1   買入1個
  2 2
   4
需要買入1個，X=2^2-3=1

4.若N=4
1 1 1 1
  2   2
    4
不需要合併，X=2^2-4=0;

5.若N=6
1 1 1 1 1 1
  2   2    2
     4     2  買入2個
     4     4
         8
需要買入兩個，X=2^3-6=2;

6.若N=9
1 1 1 1 1 1 1 1 1
  2   2    2   2  1
    4        4    1
         8      1  買入7個
          8    8
             16
需要買入7個，則X=2^4-9=7。


至此已經發現規律了，當K=1時，X=2^M-N。（M為 使2^M大於等於N的最小值
的非負整數）

對於K大於1的情況，可以把K分解為K個1，對於每個『1』進行上面的計算即可。每進行1次，K減一。
不過，需要注意的是，當K>1時，M則是使2^M小於等於N的最小值的非負整數。
  

這題我一共提交了2次，第一次20分，原因是我記錯了題目給的測試數據的大小，掛了一個2^k的表，表太小了，導致訪問了無效內存～第二次沒掛表，AC了，速度也不慢～

【我的代碼】

裸代碼RawCode

C++语言: Codee#25459

01 /*
02 *Problem: NOIP模擬題 倒水 water
03 *Author: Yee-fan Zhu
04 *GTalk: zyfworks@gmail.com
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 using namespace std;
09 //int times[15]= {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
10 int main()
11 {
12     freopen("watera.in","r",stdin);
13     freopen("watera.out","w",stdout);
14     int N,K;
15     scanf("%d %d\n",&N,&K);
16     while(K>1)
17     {
18         K--;
19         int Can=1;
20         for (int i=1;Can*2<N;i+ +)
21             Can=Can*2;
22         N=N-Can;
23         if (N==0)
24         {
25             printf("0\n");
26             return 0;
27         }
28     }
29     int Can=1;
30     for(int i=1;Can<N;i++)
31         Can=Can*2;
32     printf("%d\n",Can-N);
33     return 0;
34 }