对codejam“无限煎饼屋”解决方案的改进

我在努力解决2015年的密码问题 Infinite House of Pancakes 以最有效的方式解决问题。我目前的解决方案与 analysis (但在python中而不是c++):

def solve():
    T = int(input())  # the number of test cases

    for case in range(1, T+1):
        input()  # the number of diners with non-empty plates, ignored
        diners = [int(x) for x in input().split()]

        minutes = max(diners)  # the max stack of pancakes (= the max time)

        # try to arrange all pancakes to stacks of equal height
        for ncakes in range(1, minutes):
            s = sum([(d - 1) // ncakes for d in diners if d > ncakes])  # number of special minutes
            if s + ncakes < minutes:
                minutes = s + ncakes

        print(f'Case #{case}: {minutes}')

该方法的时间复杂度为 O(D*M) 在哪里 D 是用餐人数和 M 是煎饼的最大数量。

然而,分析也提到了另一个解决方案 O(D*sqrt(M) + M) :

虽然上面的算法足够快 解决我们的问题,我有一个更快的算法。请注意 CEIL(A/1)、CEIL(A/2)列表…最多只更改值 2×SRT(a)次。例如,如果a=10,则列表为:10、5、3、3、2、2, 2,2,2,1,1,…。该列表只改变值小于4倍。 超过2*sqrt(10)!因此,我们可以在列表更改时预计算 每个用餐者的价值仅为o(d*sqrt(m))。我们可以追踪这些 表中的值更改。例如,如果pi=10,我们可以有一个表 钛:10,-5,-2,0,-1,0,0,0,0,-1,0,…。注意前缀 这个表的和实际上是:10,5,3,3,2,2,2,…。更多 重要的是,这个表是稀疏的,即它只有O(qRT(m))。 非零。如果我们对所有ti做向量加法,我们可以得到一个表 其中前缀sum的索引x处的每个条目都包含 CEIL(PI/X)。然后,我们可以在代码中计算ceil(pi/x)-1的和 上面用数字减去前缀和的第x个索引 用餐者。因此,只需要另一个o(m)过程来计算 候选答案,这给了我们O(d*sqrt(m)+m)运行时间。一 更快的解决方案!

有谁能给我一个提示如何把它翻译成python吗?