描述分工合理的步骤

描述分工合理的步骤

我们有一大堆工作要做，所有的工作都被分配了若干工作，工作量将是一个整数，可能是正数、负数或零。

吉姆和鲍勃的工作是做所有的工作，但是我们需要找到容器中可以进行分配的位置，这样吉姆和鲍勃就可以有最平均的工作量来执行。

你的任务是写一个函数，确定为Jim和Bob分担工作量的地方，它将被提供一个难度评级的容器，你必须返回一个元组/数组，其中包含（分担的最佳位置，两个总工作量的差值）。如果没有提供工作负载，则返回(None，None)

实例
我们要分割的工作负载如下。

split_workload([1, 6, 2, 3, 5, 4, 1])

如果我们在每个位置尝试切割，那么。

  分配吉姆的工作 鲍勃的工作    比率 差异
0 [], [1, 6, 2, 3, 5, 4, 1] 0:22 22
1 [1] [6, 2, 3, 5, 4, 1] 1:21 20
2 [1, 6] [2, 3, 5, 4, 1] 7:15 8
3 [1, 6, 2] [3, 5, 4, 1] 9:13 4
4 [1, 6, 2, 3] [5, 4, 1] 12:10 2
5 [1, 6, 2, 3, 5] [4, 1] 17:5 12
6 [1, 6, 2, 3, 5, 4] [1] 21:1 20
7 [1, 6, 2, 3, 5, 4, 1] [] 22:0 22

正如你所看到的，当我们在第4位分割时，我们得到了最均匀的分割，只有2的差异。

因此，对于我们的例子，结果将是。

split_workload([1, 6, 2, 3, 5, 4, 1]) -> (4, 2)

如果你的答案在O(n)时间和内存限制下运行，你会得到自我奖励的分数。

列表算法

1st. solution

def split_workload(workload):
    if not workload: return None, None
    
    diff = sum(workload)    
    best_i, best_diff = None, float('inf')
    
    for i, work in enumerate(workload):
        if abs(diff) < best_diff:
            best_i, best_diff = i, abs(diff)
        
        # 每右移1步，左右两边的工作量之差
        # 减少 2*workload[i]
        diff -= 2*work
    
    return best_i, best_diff

2nd. solution

def split_workload(workload):
    if not workload: return (None, None)
    diff = [0,float('inf')]
    for i in range(len(workload)):
        d = sum(workload[:i]) - sum(workload[i:])
        if abs(d) < diff[1]:
            diff[0],diff[1] = i,abs(d)

    return tuple(diff)

本文由mdnice多平台发布