coding everyday

每個(gè)杯子的容量為C升，從塔頂?shù)瓜翷升水，當(dāng)1號(hào)杯子滿了之后，會(huì)等量溢出到2號(hào)和3號(hào)杯子。當(dāng)2號(hào)和3號(hào)滿了，2號(hào)溢出到4號(hào)和5號(hào)，3號(hào)溢出到5號(hào)和6號(hào)，注意5號(hào)接受來(lái)自兩個(gè)杯子的水。依次類(lèi)推。給定C和L，請(qǐng)問(wèn)，第n杯里有多少水。

分析：（出題的人貌似是讓用動(dòng)態(tài)規(guī)劃的方式來(lái)做，可是偶不懂動(dòng)態(tài)規(guī)劃哦。。用我自己的思路來(lái)做。）

可以看到這些杯子里面就兩類(lèi)，一類(lèi)就是靠邊的杯子，還有一類(lèi)就是中間的，靠邊的杯子只能從它上面的一個(gè)杯子接水，而中間的可以從上面的2個(gè)杯子接水，我覺(jué)得這可以用分治算法的思路來(lái)做這個(gè)題目，因?yàn)榈紫卤铀亩嗌偃Q于它上面的杯子，上面的杯子又取決于再上面的。

之前說(shuō)過(guò)了，杯子就兩類(lèi)，一類(lèi)就是靠邊的，還有一類(lèi)是中間的；對(duì)于靠邊的，它只能從它上面的一個(gè)杯子里面得到溢出的水的一半；中間的，可以得到它上邊左邊溢出的一半和右邊溢出的一半。這邊有個(gè)小問(wèn)題，就是如果我們按照最終一個(gè)杯子里的水的數(shù)量來(lái)做的話，有問(wèn)題，比如第1個(gè)杯子，它最終只有cL的水，對(duì)吧？但是我們應(yīng)該當(dāng)NL來(lái)考慮。所以這里我們考慮的杯子的水是所有流經(jīng)它的數(shù)量，而非最終數(shù)量。

那現(xiàn)在的問(wèn)題就是，找出來(lái)特定杯子的水從哪來(lái)就OK了。靠邊的是從上面來(lái)，并且同一行的2個(gè)靠邊的是一樣的，所以只需要考慮上一行靠邊的溢出的/2就OK了。中間的（如5），它從2和3來(lái)的，可以看出來(lái)2和3分別是它上一行的左邊一個(gè)杯子和上一行相同位子的杯子。可以擴(kuò)展幾層驗(yàn)證一下。所以最后的問(wèn)題就是如果把n轉(zhuǎn)換成第x層的第y個(gè)位子，就這么簡(jiǎn)單。

代碼如下：

 1 template<int N, int c>
 2 float get_unlimited_wine_amount(int x, int y) {
 3     if (x == 1 && y == 1) {
 4         return N;
 5     }
 6 
 7     float ret = 0;
 8     if (y == 1 || y == x) {
 9         ret = 1.0 * (get_unlimited_wine_amount<N, c>(x-1, 1) -c ) /2;
10         return ret > 0 ? ret : 0;
11     }
12 
13     float left = get_unlimited_wine_amount<N, c>(x-1, y-1) - c;
14     left = left > 0 ? left : 0;
15     float right = get_unlimited_wine_amount<N, c>(x-1, y) - c;
16     right = right > 0 ? right : 0;
17     ret = (left + right) / 2;
18     return ret > 0 ? ret : 0;
19 }
20 
21 map<int, float> val;
22 
23 template<int N, int c>
24 float get_wine_amount(int n) {
25     float ret = 0, x, y;
26 
27     for (x = 1; ;x++) {
28         if (((x + 1) * x)/2 >= n)
29             break;
30     }
31 
32     y = n - ((x - 1) * x)/2;
33 
34     ret = get_unlimited_wine_amount<N, c>(x, y);
35     val.insert(make_pair(n, ret));
36 
37     return ret > c ? c : ret;
38 }

出題者的參考答案