Codingame「简单负载均衡」问题优化方案求助

你的问题出在逐个分配任务后重复排序的逻辑上，时间复杂度为O(k*n logn)，当k极大时（比如百万级甚至更大），排序的重复开销会直接导致超时。我们可以通过批量计算任务分配来彻底解决性能问题，避免逐个处理任务。

优化核心思路 #

不再每次给单台服务器加任务后重新排序，而是计算「能一次性把多少台服务器提升到下一个负载层级」，批量消耗任务数：

1. 先对服务器负载数组排序（仅需一次，O(n logn)时间）。
2. 遍历数组，找到当前连续的最小负载服务器数量count，以及下一个更高的负载值next_val。
3. 计算把这count台服务器都提升到next_val需要的任务数tasks_needed = (next_val - current_min) * count：
   • 若剩余任务数k >= tasks_needed，则扣除这些任务，更新当前最小负载为next_val，继续循环处理下一层级。
   • 若k < tasks_needed，则将剩余任务批量分配：每台服务器先加k//count个任务，剩下的k%count台服务器再加1个，直接计算最终的最大/最小负载差值。
4. 若所有服务器已达到同一负载，剩余任务分配后差值只能是0（k能被n整除）或1（k不能被n整除）。

优化后的代码 #

n = int(input())
k = int(input())
arr = list(map(int, input().split()))
arr.sort()

i = 0
current_min = arr[i]
while k > 0:
    # 统计当前最小负载的服务器数量
    count = 0
    while i < n and arr[i] == current_min:
        count += 1
        i += 1
    
    # 获取下一个负载值，遍历完所有服务器则设为无穷大
    next_val = arr[i] if i < n else float('inf')
    delta = next_val - current_min
    tasks_needed = delta * count
    
    if k >= tasks_needed:
        # 足够将count台服务器提升到next_val，扣除任务数
        k -= tasks_needed
        current_min = next_val
    else:
        # 剩余任务不足以提升到next_val，批量分配
        add_per_server = k // count
        remainder = k % count
        final_min = current_min + add_per_server
        # 最终最大负载取原数组最大值和部分服务器新负载的较大者
        final_max = max(arr[-1], current_min + add_per_server + (1 if remainder else 0))
        print(final_max - final_min)
        exit()

# 任务全部分配完毕，计算最终差值
print(arr[-1] - current_min)

复杂度说明 #

• 排序阶段：O(n logn)
• 遍历数组阶段：O(n)
• 整体时间复杂度为O(n logn)，完全不受k的大小影响，即使k是1e18量级也能瞬间处理。

内容的提问来源于stack exchange，提问作者Kernel-rb