c

codeye

V1

2022/10/13阅读:16主题:默认主题

描述分工合理的步骤

描述分工合理的步骤

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

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

你的任务是写一个函数,确定为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)

分类:

后端

标签:

后端

作者介绍

c
codeye
V1