coding everyday

每个杯子的容量为C升，从塔顶倒下L升水，当1号杯子满了之后，会等量溢出到2号和3号杯子。当2号和3号满了，2号溢出到4号和5号，3号溢出到5号和6号，注意5号接受来自两个杯子的水。依次类推。给定C和L，请问，第n杯里有多少水。

分析：（出题的人貌似是让用动态规划的方式来做，可是偶不懂动态规划哦。。用我自己的思路来做。）

可以看到这些杯子里面就两类，一类就是靠边的杯子，还有一类就是中间的，靠边的杯子只能从它上面的一个杯子接水，而中间的可以从上面的2个杯子接水，我觉得这可以用分治算法的思路来做这个题目，因为底下杯子水的多少取决于它上面的杯子，上面的杯子又取决于再上面的。

之前说过了，杯子就两类，一类就是靠边的，还有一类是中间的；对于靠边的，它只能从它上面的一个杯子里面得到溢出的水的一半；中间的，可以得到它上边左边溢出的一半和右边溢出的一半。这边有个小问题，就是如果我们按照最终一个杯子里的水的数量来做的话，有问题，比如第1个杯子，它最终只有cL的水，对吧？但是我们应该当NL来考虑。所以这里我们考虑的杯子的水是所有流经它的数量，而非最终数量。

那现在的问题就是，找出来特定杯子的水从哪来就OK了。靠边的是从上面来，并且同一行的2个靠边的是一样的，所以只需要考虑上一行靠边的溢出的/2就OK了。中间的（如5），它从2和3来的，可以看出来2和3分别是它上一行的左边一个杯子和上一行相同位子的杯子。可以扩展几层验证一下。所以最后的问题就是如果把n转换成第x层的第y个位子，就这么简单。

代码如下：

 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 }

出题者的参考答案