对列表进行重新排序，使之前所有的数字之和尽可能小于当前的numb

Question

我遇到了这样一个问题，一个停车场里有车，每个司机都要花一定的时间停车，如果一个司机要等的时间超过他停车的时间，他就会不高兴，这意味着排在他前面的司机总要花更多的时间停车。我想找到一个序列，它可以最小化队列中的驱动程序。例如： 2 15 1 5 3-->；是行中的驱动程序顺序。第一个司机显然会很高兴，因为他们不必等待任何人，第二个在排队（15）需要15分钟停车，但只需等待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

使用一个for循环：

import random

# set num drivers
NUM_DRIVERS = 5
# set max wait time
MAX_WAIT_TIME = 20

# create driver parking list - max out at 20 min parking job
parking = [random.randint(1, MAX_WAIT_TIME) for _ in range(NUM_DRIVERS)]

parking
# [20, 16, 4, 4, 2]

def happy_drivers(parking_list):
    """
    happy_drivers takes an input list and returns a custom ordered 
    list of driver wait times before they become unhappy. 

    Each item in the list contains the maximum amount of time 
    a driver is willing to wait to park a vehicle before they become
    unhappy. Additionally, this wait time also corresponds to how long it 
    takes them to park a vehicle. 

    Take an input list [20, 10, 4, 4, 2]. An optimal happy ordering 
    could be parking cars in [2, 4, 10, 20, 4] where there are 4 happy drivers. 
    If the drivers were simply sorted, i.e. [2, 4, 4, 10, 20], 
    there would only be 2 happy drivers. 

    Parameters
      -
    parking_list - list
        Input list of maximum wait times per driver

    Returns
      -
    new_driver_list - list
        Sorted driver list based on creating the fewest unhappy
        drivers

    happy_driver_idx - int
        Number of happy drivers who didn't have to wait longer
        than their max wait time
    """
    # sort parking
    sorted_parking = sorted(parking_list)
    cur_wait = 0
    new_driver_list = []
    happy_driver_idx = 0
    for i, item in enumerate(sorted_parking):
        if item > cur_wait:
            cur_wait += item
            new_driver_list.insert(happy_driver_idx, item)
            happy_driver_idx += 1
        else:
            new_driver_list.append(item)

    return new_driver_list, happy_driver_idx

optimal_ordering, happy_drivers = happy_drivers(parking)
print("""An optimal ordering: {}\nNum happy drivers: 
     {}""".format(optimal_ordering, happy_drivers))

# An optimal ordering: [2, 4, 16, 4, 20]
# Num happy drivers: 3

Answer 2

简单使用列表.排序（）按升序/降序排列数字的函数。有关更多信息，请参阅帮助(列表.排序（））在ipython笔记本中

Answer 3

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

#!/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()