---
tags: 演算法
---

# 關於優化ㄉ小問題

## 小麻煩

圖中第二列是code執行所花毫秒。code是對的，只是有幾筆測資會給特別大的數字，如 1<di<1000000；作業繳交系統看你運行時間太久就不會給你對。不知道怎麼優化QQQQQQ

我想是因為包三層迴圈的關係，但我好像也想不到比較好的替代方案。

# 我ㄉcode

line1 = input().split(",")
m = int(line1[0])
n = int(line1[1])
P = input().split(",")
for j in range(n):
    P[j] = int(P[j])
D = input().split(",")
for j in range(n):
    D[j] = int(D[j])

T = [0]*m
totalDelayTime = 0

pdiLst = []
for i in range(n):
    pdiLst.append([P[i], D[i], i])

while len(pdiLst) > 0:
    delayMatrix = []
    for j in range(len(pdiLst)):
        temp = []
        for i in range(m):
            temp.append(T[i] + pdiLst[j][0] - pdiLst[j][1])
        temp.append(pdiLst[j][2])   # 最後一行是每個job的index
        delayMatrix.append(temp)

    minimum = delayMatrix[0][0]
    for j in range(len(pdiLst)):
        for i in range(m):
            if delayMatrix[j][i] <= minimum:
                minimum = delayMatrix[j][i]

    jiLst = []
    for j in range(len(pdiLst)):
        for i in range(m):
            if delayMatrix[j][i] == minimum:
                jiLst.append([delayMatrix[j][m], i])
    # 倘若有多組(j, i)都擁有相同最小值，則先挑選機台編號最小者，機台編號相同的話就再挑選工作編號最小者
    jiLst.sort(key=lambda c:(c[1],c[0]))
    jiLst = jiLst[:1]
    j = jiLst[0][0]
    i = jiLst[0][1]

    # 更新時間
    if (T[i] + P[j] - D[j]) > 0:
        totalDelayTime = totalDelayTime + T[i] + P[j] - D[j]
    T[i] += P[j]

    # 將該工作移除 !
    delIndex = 0
    for i in range(len(pdiLst)):
        if pdiLst[i][2] == j:
            delIndex = i
    pdiLst = pdiLst[:delIndex] + pdiLst[delIndex+1:]

print(totalDelayTime)

# Retry!

line1 = input().split(",")
m = int(line1[0])
n = int(line1[1])
P = input().split(",")
for j in range(n):
    P[j] = int(P[j])
D = input().split(",")
for j in range(n):
    D[j] = int(D[j])

T = [0]*m


pdiLst = []
for i in range(n):
    pdiLst.append(P[i]-D[i])
res = 0

while n!= 0:
    min_T = 0
    pdi_diff = 0
    if min(T) < T[min_T]:
        min_T = T.index(min(T))
    
    if min(pdiLst) <pdiLst[pdi_diff]:
        pdi_diff = pdiLst.index(min(pdiLst))
    if T[min_T] + pdiLst[pdi_diff] > 0:
        res += T[min_T] + pdiLst[pdi_diff]
    T[min_T] += P[pdi_diff]
    pdiLst.pop(pdi_diff)
    P.pop(pdi_diff)
    n -=1

print(res)