Python性能算法：环状不均等分弹珠问题

嘿，这个问题如果直接模拟每一步分配，遇到大数量弹珠时肯定会卡得不行，所以咱们得换个思路——用数学推导+二分查找来搞，既能保证性能，又能准确算出结果。下面我一步步给你拆解：

先理清楚问题规则 #

k个男孩围成圈，首领先拿1颗，左边的男孩接着拿2颗，再左边拿3颗……每个男孩拿的数量都比他右边刚拿的多1颗，直到弹珠分完，最后一个人可能拿不够理论数量。

数学推导：避免傻循环的关键 #

1. 完整轮次的弹珠消耗 #

每一轮（所有男孩都拿一次）的弹珠数是等差数列：

• 第1轮：1+2+…+k = k*(k+1)//2
• 第2轮：每个人都比第一轮多拿k颗（因为一圈下来，下一轮的起始数比上一轮起始数多k），所以总消耗是第一轮的数 + k²
• 经过推导，m轮完整分配后，总消耗弹珠数 = m * k * (k*m + 1) // 2

2. 快速找到最大完整轮次m #

我们需要找到最大的m，使得m轮的总消耗不超过总弹珠数n。这里用二分查找最快，不用从0开始一个个试，时间复杂度是O(log(max_m))，哪怕n是上亿级别的都能瞬间出结果。

3. 处理剩余弹珠 #

算出完整轮次后，剩下的弹珠从首领开始继续分配：第1个男孩该拿m*k +1颗，第2个拿m*k+2颗……直到把剩下的弹珠分完，最后一个拿的人可能只能拿到剩余的数量。

Python代码实现 #

def distribute_marbles(total_marbles: int, boy_count: int) -> list:
    # 边界情况处理
    if boy_count == 0:
        return []
    if total_marbles == 0:
        return [0] * boy_count
    
    # 二分查找最大的完整分配轮次
    left, right = 0, int((2 * total_marbles / boy_count**2)**0.5) + 2
    max_full_rounds = 0
    while left <= right:
        mid_rounds = (left + right) // 2
        consumed = mid_rounds * boy_count * (boy_count * mid_rounds + 1) // 2
        if consumed <= total_marbles:
            max_full_rounds = mid_rounds
            left = mid_rounds + 1
        else:
            right = mid_rounds - 1
    
    # 计算每个男孩在完整轮次中获得的弹珠数
    result = [
        max_full_rounds * (2 * i + boy_count * (max_full_rounds - 1)) // 2
        for i in range(1, boy_count + 1)
    ]
    
    # 处理剩余弹珠
    remaining = total_marbles - max_full_rounds * boy_count * (boy_count * max_full_rounds + 1) // 2
    next_take = max_full_rounds * boy_count + 1  # 下一个该拿的数量
    for idx in range(boy_count):
        if remaining <= 0:
            break
        take = min(next_take, remaining)
        result[idx] += take
        remaining -= take
        next_take += 1
    
    return result

# 测试示例
if __name__ == "__main__":
    # 测试：25颗弹珠，3个男孩
    print(distribute_marbles(25, 3))  # 输出: [9, 7, 9]
    # 验证：第一轮1+2+3=6，第二轮4+5+6=15，剩余4；首领拿4颗，总数1+4+4=9，第二个2+5=7，第三个3+6=9

为什么这个算法高效？ #

• 二分查找找轮次：避免了O(m)的循环，直接把这部分复杂度降到O(log(m))
• 剩余弹珠处理：最多循环k次（男孩数量），k一般不会特别大，所以这部分可以忽略不计
• 整体时间复杂度是O(k + log(m))，哪怕n是10^18级别的都能快速算出结果

内容的提问来源于stack exchange，提问作者user9699361