往一叠玻璃杯中加水

Question

我一直想知道帕斯卡三角形是否有任何实际应用，而不仅仅是二项式展开的系数。

我试图解决这个问题：

但是，如果我要添加 K 个单位的水并想找到一个水最少的玻璃杯怎么办：

其中，Glass 将被发现为：第 r 行中的第 c 个玻璃

我相信。如果我们能找到这个，那么我们就不难找到任何玻璃杯中的水量 {i<r and j<c}

问题：

输入加水-K单位，每杯容量为1-单位

预期输出：第r行第c个玻璃杯中的水最少。

我试图通过记录每行开始溢出时的容量来解决问题：并想知道如何继续使用这种方法。

      1       max = 1, cap = 1
     1 1      max = 1, sum(coefficients)=2**1 = 2, cap = 2/1 
    1 2 1     max = 2, sum = 2**2, cap = 4/2 = 2 units 
   1 3 3 1    max = 3, sum = 2**3, cap = 8/3 units
  1 4 6 4 1   max = 6, sum = 2**4, cap = 16/6 units

#不确定，但在我看来，@which water is being added.

                 1
              1/2   1/2
           1/4   2/4  1/4
        1/8   3/8    3/8   1/8
     1/16  4/16  6/16   4/16  1/16

我应该使用二维列表并定义为：

Δ1, Δ2 = 0, 0
if g(n-1, k)>1 and k <= n-1:
    Δ1 = g(n-1, k) -1 
if g(n-1, k-1)>1 and k-1 <= n-1:
    Δ2 = g(n-1, k-1) - 1
g(n, k) = Δ1/2 + Δ2/2

g(n,k) = g(n-1, k-1) + g(n-1, k)

g = [[0]*(i+1) for i in range(11)]
def f(g, K):
    g[1][1] += 1
    K = K-1
    d1, d2 = 0, 0
    for n in range(2, 10):
        for k in range(1, n+1):
            if k ==1:
                g[n][k] = g[n-1][k]/2
            if k == n:
                g[n][k] = g[n-1][k-1]/2
            else:
                if g[n-1][k-1]>1:
                    d1 = g[n-1][k-1] -1
                if g[n-1][k] > 1:
                    d2 = g[n-1][k] -1
                g[n][k] = d1/2 + d2/2        
    return g, K
k = int(input())
while k:
    g, k = f(g, k)
for x in g:
    print(x)

不知道少了什么？

Answer 1

对于这么小的K约束，简单的逐行填充就足够了（我们可以只存储两行，这里为简单起见使用二维列表）

def fillGlasses(k, row, col):
    gl = [[k]]
    level = 1
    overflow_occured = True
    while overflow_occured:   # also can stop when at needed row
        print(gl[level-1])  #before overflow
        level += 1
        overflow_occured = False
        gl.append([0]*level)
        for i in range(level - 1):
            t = gl[level-2][i] - 1
            if t > 0:
                gl[level-1][i] += t/2
                gl[level-1][i+1] += t/2
                gl[level-2][i] = 1
                overflow_occured = True
    #print(gl)  #after all
    return gl[row-1][col-1]

print(fillGlasses(21,8,4))

[21]
[10.0, 10.0]
[4.5, 9.0, 4.5]
[1.75, 5.75, 5.75, 1.75]
[0.375, 2.75, 4.75, 2.75, 0.375]
[0, 0.875, 2.75, 2.75, 0.875, 0]
[0, 0, 0.875, 1.75, 0.875, 0, 0]
[0, 0, 0, 0.375, 0.375, 0, 0, 0]
0.375

Answer 2

我猜你是在问这个在线裁判问题，或者一个非常相似的问题：https://practice.geeksforgeeks.org/problems/champagne-overflow2636/1

如果是这样，实际上 R 和 C 的约束只有 500，任何模拟都可以。一个小问题是，即使前一行没有完全装满，也可能连续有水。你可以考虑小的测试用例，模拟一下，比如K = 6，眼镜看起来像：

1
1, 1
0.75, 1, 0.75
0, 0.25, 0.25, 0 
// Notice previous row is not fully filled, makes sense as "middle" glasses will overflow faster

我认为在实现方面，自上而下和自下而上的方法是相似的。这是我自上而下接受的代码，它简单地模拟了倒水和溢出过程，使用C++，可以用任何语言实现相同的算法：

class Solution {
    public:
    double cups[505][505];

    void pourWaterAt(double K, int R, int C, int targetR){
        if(R > targetR) return;
        cups[R][C] += K;
    
        if(cups[R][C] > 1){
            double overflow = cups[R][C] - 1;
            cups[R][C] = 1;
            pourWaterAt(overflow/2.0f, R+1, C, targetR);
            pourWaterAt(overflow/2.0f, R+1, C+1, targetR);
        }
    }

    double waterOverflow(int K, int R, int C) {
        memset(cups, 0, sizeof(cups));
        pourWaterAt(K, 1, 1, R);
        return cups[R][C];
    }
};

模拟完成后，只需扫描cups[R][C]并找到最小的正数（及其索引）即可得到答案。

往一叠玻璃杯中加水

Adding water to stack of glasses

python

algorithm

math

graph-algorithm

pascals-triangle