Aziz & Prakash 2021问题3.7：最小化最大负载服务器分配算法的代码实现问询

首先得明确一个关键前提：必须先把用户按哈希值从小到大排序。因为题目中的分配规则是“哈希值处于K_j与K_j+1之间的用户分配到服务器j”，等价于按哈希排序后，用户是连续的区间分配给服务器——这是整个动态规划思路成立的基础，千万不能漏掉这一步！

接下来我们一步步把思路转化为可执行的代码：

1. 预处理：前缀和数组 #

首先计算前缀和数组，用来快速获取任意区间用户的数据总和。假设我们已经把用户的B值按哈希排序后存在列表B中，前缀和数组sum_b定义为：

• sum_b[0] = 0
• sum_b[a] = B[1] + B[2] + ... + B[a]（对应前a个用户的总数据量）

这样，第x+1到a个用户的总数据量就是sum_b[a] - sum_b[x]，可以O(1)时间计算。

2. 动态规划表定义 #

我们用二维数组dp，其中dp[b][a]表示把前a个用户分配到b台服务器时，能实现的最小最大负载。

初始化规则 #

• 当只有1台服务器时（b=1），所有用户都在这台服务器上，所以dp[1][a] = sum_b[a]
• 当用户数a小于服务器数b时，每个服务器最多分配1个用户，此时最大负载就是单个用户的最大B值（不过题目中通常满足n≥m，这个情况作为边界处理即可）

3. 递推逻辑+二分查找优化 #

对于每个服务器数b（从2到m），每个用户数a（从b到n，因为至少每个服务器分配1个用户），我们需要找到一个x（范围是b-1 ≤ x ≤ a-1），使得max(dp[b-1][x], sum_b[a] - sum_b[x])最小。

正如书中所说，x增大时：

• dp[b-1][x]是递增的（前x个用户分配到b-1台服务器的最小最大负载，用户越多，这个值不会变小）
• sum_b[a] - sum_b[x]是递减的（剩下的用户越少，总数据量越小）

两者的最大值的最小值出现在两者“交叉”的位置，因此可以用二分查找快速定位最优x，而不需要遍历所有可能的x。

4. 代码实现（Python示例） #

def min_max_server_load(B, m):
    # 第一步：按哈希值排序用户的B值（实际场景需要先按h_i排序，这里假设输入已排序）
    B_sorted = sorted(B)
    n = len(B_sorted)
    
    # 边界处理：服务器数≥用户数，最大负载为单个用户的最大数据量
    if m >= n:
        return max(B_sorted)
    
    # 第二步：构建前缀和数组（索引0到n，sum_b[0]=0，sum_b[a]对应前a个用户的总和）
    sum_b = [0] * (n + 1)
    for a in range(1, n+1):
        sum_b[a] = sum_b[a-1] + B_sorted[a-1]
    
    # 第三步：初始化DP表，dp[b][a]表示b台服务器分配前a个用户的最小最大负载
    dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    
    # 初始化1台服务器的情况
    for a in range(1, n+1):
        dp[1][a] = sum_b[a]
    
    # 递推计算b从2到m的情况
    for b in range(2, m+1):
        for a in range(b, n+1):
            left = b-1
            right = a-1
            best_max = float('inf')
            
            # 二分查找最优x
            while left <= right:
                mid = (left + right) // 2
                current_max = max(dp[b-1][mid], sum_b[a] - sum_b[mid])
                
                # 更新当前最优的最大负载
                if current_max < best_max:
                    best_max = current_max
                
                # 调整二分区间：让两部分负载尽可能接近
                if dp[b-1][mid] < sum_b[a] - sum_b[mid]:
                    left = mid + 1
                else:
                    right = mid - 1
            
            # 检查二分结束后的相邻点，避免错过最优解
            for x in [right, left]:
                if b-1 <= x <= a-1:
                    current_max = max(dp[b-1][x], sum_b[a] - sum_b[x])
                    if current_max < best_max:
                        best_max = current_max
            
            dp[b][a] = best_max
    
    # 返回最终结果：m台服务器分配n个用户的最小最大负载
    return dp[m][n]

# 测试用例
if __name__ == "__main__":
    # 示例：5个用户，2台服务器，B值排序后为[1,2,3,4,5]
    B = [3,1,4,2,5]
    m = 2
    print(min_max_server_load(B, m))  # 输出9，对应前3个用户总和6分配到第一台，后2个总和9到第二台

关键细节解释 #

• 排序的必要性：如果不按哈希排序，用户的区间分配就不是连续的，动态规划的状态定义dp[b][a]就不成立，因为前a个用户不一定对应一个哈希区间。
• 二分查找的调整逻辑：当dp[b-1][mid] < sum_b[a]-sum_b[mid]时，说明当前前半部分的负载更小，我们可以尝试增大x，让前半部分的负载增加，后半部分的负载减少，从而让两者的最大值更小；反之则减小x。
• 相邻点检查：二分查找结束后，最优解可能在right或left的位置，所以需要额外检查这两个点，避免因为整数二分的精度问题错过最优值。

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