python - 重新排序列表，尽可能使所有先前数字的总和小于当前数字

Question

我遇到过这样一个问题， parking 场里面有车，每个司机都拿了一定数量的车停好，等的时间多了司机会不高兴他需要 parking ，这意味着排在他前面的司机总共需要更多的时间来 parking 。我想找到一个序列，它可以最大限度地减少线路中的驱动程序。例如: 2 15 1 5 3 --> 是行中驱动程序的顺序。第一个司机显然会很高兴，因为他们不必等待任何人，第二个 (15) 需要 15 分钟才能 parking ，但只需要等待 2 分钟，所以他也会很高兴，问题从第三个开始司机等。我想重新排列它们，以便将不满意的司机数量降至最低。我想出了一个解决方案，可以找到列表中项目的所有排列，并为每个项目找到不满意的司机，但是当司机数量大量增加时，它似乎非常慢。我的代码是

import itertools
driverList = input().split()
for i in range(len(driverList)):
    driverList[i] = int(driverList[i])


permutationList = []
permutationList += list(itertools.permutations(driverList))

maxCount = 1
for i in range(len(permutationList)):
    count = 1
    sumCount = permutationList[i][0]
    for j in range(1, len(permutationList[i])):
        if permutationList[i][j] > sumCount:
            count += 1
        sumCount += permutationList[i][j]
    if count > maxCount:
        maxCount = count

print(maxCount)

我可以利用任何其他方法或数据结构来使该算法更加高效吗？非常感谢。 输入“2 15 1 5 3”的答案将是 4，给出这个答案是因为如果汽车按照“1 3 5 2 15”的顺序重新排列，快乐司机的数量将是 4。

• 1 > 0(快乐)
• 3 > 1(快乐)
• 5 > 3+1(快乐)
• 2 < 5+3+1(不开心)
• 15 > 2+5+3+1(快乐)

Answer 1

我还没有证明这是正确的，但我想不出任何反例，而且它是有效的。请注意对原始代码的许多样式改进。

#!/usr/bin/env python3

def happiest_drivers(drivers):
    drivers = sorted(drivers)
    assert drivers and drivers[0] > 0
    rv = []
    wait = 0
    # First, repeatedly find the fastest driver who will be happy.
    for i, d in enumerate(drivers):
        if d > wait: # or >= if that makes more sense
            rv.append(d)
            drivers[i] = 0
            wait += d
    num_happy = len(rv)
    # Then add all the unhappy drivers. There's nothing we can do about them.
    for d in drivers:
        if d:
            rv.append(d)
    return rv, num_happy

def main():
    order, num_happy = happiest_drivers([int(x) for x in input().split()])
    print('%d/%d happy with order %r' % (num_happy, len(order), order))

if __name__ == '__main__':
    main()