python - Python 性能算法中的不均匀共享

Question

一组 k 个男孩，应该按如下方式支付弹珠:他们坐成一圈，每个男孩将比他右边的男孩多拿 1 个弹珠，并将装有剩余弹珠的袋子传给他左边的男孩。

领导者首先为自己取出 1 个弹珠。他将袋子递给左边的男孩，然后男孩为自己取出 2 个弹珠，并将袋子递到他的左边。然后那个男孩拿了 3 个硬币，把袋子递到他的左边，依此类推。这个过程一直持续到袋子空了(最后一个从袋子里拿走的男孩可能得不到他应该得到的弹珠)。

我想获得 LEADER 在过程结束时收到的弹珠总数。

这就是我所拥有的，它可以工作但是太慢了:

def countMarbles(n, k):
    c = 0
    leader = 0
    while n>0:
        for i in range(k):
            c+=1
            if i == 0:
                if c<=n:
                    leader += c
                else:
                    leader += n
            n -= c
    return leader

Answer 1

您正在加速的弹珠是 1，然后是 2，然后是 3...这种求和有一个公式，1到x的和是(x)(x + 1)/2。

现在给你 n，想知道你能把袋子穿过多少次。这意味着获得最高的 x，使得 (x)(x + 1)/2 小于或等于 n。

我们可以通过求解 0 = x^2 + x - 2n 得到这个。我们可能会在那里得到一个小数结果，所以我们应该取方程正答案的底值。

一旦找到正确的 x，我们就知道袋子每经过 k 次，就有 1 次交给领导者。他首先得到 1 个弹珠，然后他得到 k + 1 个弹珠，然后是 2k + 1 ...

如果有 x 次传球，则 x/k 的 ceil 传给领导者。取出始终为 1 的第一遍，我们得到 l = ceil(x/k) - 1 具有大于 0 的 k 系数的遍:((k + 1) + (2k + 1) + ... + (lk + 1)) = (1 + 2 + 3 + ... + l) * k + l = (l * (l + 1)/2) * k + l.

考虑到 leader 从 1 开始，解决方案是 (l * (l + 1)/2) * k + l + 1

唯一的问题是袋子里剩下的弹珠怎么办。在那些应该交给领导者的情况下，我们还需要考虑他们。要做到这一点，x 必须是 k 的倍数，这意味着我们完成了这一轮，所以下一轮应该是领先者，但没有足够的弹珠来进行另一轮。

这是一个 python 实现:

import math

def solve (n, k):
    x = math.floor((-1 + math.sqrt(1 + 8*n)) / 2)
    l = math.ceil(x / k) - 1
    sol = (l * (l + 1) / 2) * k + l + 1
    if x % k == 0 :
        sol += n - (x * (x + 1) / 2)
    return int(sol)