所有车的过桥最短时间

今晚帮朋友助攻遇到了一道题，当时有思路但是没有写出来，后来结合牛客网上的解答写了出来，也不知道具体能AC多少道题，先放在这里等大家指点吧~

• 题目描述

有N辆车药陆续通过一座最大承重为W的桥，其中第i辆车的重量为w[i]，通过桥的时间为t[i]，要求第i辆车上桥的时间不早于第i-1辆车上桥的时间，任意时刻桥上所有车辆的总重量不超过W。

那么，所有车辆都通过这座桥所需的最短时间为多少？

输入：

第一行为两个整数N,W(1<N,W<=100000)

第二行输入N个整数w[1]到w[N] (1<=w[i]<=W)

第三行输入N个整数t[1]到t[N]

• 解题思路

  维护一个上桥的优先队列curIdx表示当前哪些车辆在桥上，比较的是下车时间。

  如果当前车辆<桥还能承载的重量，车子上桥，车子下桥的时间需要更新为"已经花费的时间+过桥时间"；否则，车子不能上桥，同时让已经上桥的车下桥，并更新"已经花费的时间"。

def func(N, totalW, W, T):
    if N ==1:
        return T[0]
    sumT, curW = 0, 0  # sumT表示已经花费的时间 curW表示当前桥上承载的重量
    carsIdx = []    # 表示目前桥上承载着的车的索引
    i = 0
    while i < N:
        # 如果重量允许下一辆上车，则更新
        if curW + W[i] <= totalW:
            T[i] += sumT  # 第i辆车的下车时间=已花费的时间+过桥时间
            carsIdx.append(i)
            curW += W[i]
            i += 1
        else:
            tmp = []
            for idx in carsIdx:
                tmp.append(T[idx])
            minT = min(tmp)   # 找出已上桥的车中最早下桥的车，记录该车下桥的时间
            j = 0
            while j < len(carsIdx):    # 该时刻下桥的车可能不止一辆
                if T[carsIdx[j]] == minT:
                    curW -= W[carsIdx[j]]
                    carsIdx.pop(j)
                else:
                    j += 1
            sumT = minT   # 更新已花费的时间，即为最早下车时间
    sumT = T[-1]   # 返回最后一辆车下车的时间
    return sumT

if __name__ == '__main__':
    N, totalW = 4, 2
    W = [1, 1, 1, 1]
    T = [2, 1, 2, 2]
    print(func(N, totalW, W, T))
           

对于例子中的情况，t=0时刻第1辆和第2辆车上桥，t=1时刻第2辆车下桥，同时第3辆车上桥，t=2时刻第1辆车下桥，同时第4辆车上桥，t=3时第3辆车下车，t=4时第4辆车下车。