APCS Nov 2021 - g597 Q3 [Python]

本題敘述： 有 n 台機器排成一直線, 每一個機器都有一個數值t[i], 代表該台機器要產出一單位的資料需要t[i]單位的時間，接下來有 m 個工作要完成, 每一個工作都需要位置在[l[i],r[i]]的機器各生產出w[i]單位資料，現在你可以調換n台機器的順序, 目標是使得這m個工作做完的總時間要最小。

[name=BlackInk7777] 這如果用迴圈慢慢加絕對會超時，所以要使用差分數組來讓這題快一點。

---

差分數組解釋：

假設我們有一個初始都為零的數組 dur，大小為 5，如下： Array= [0,0,0,0,0] 假設要在[2,5]內所有元素上加 1、要在[3,5]內所有元素上加 2：

使用差分數組實現

1. 初始化差分數組 diff： diff = [0, 0, 0, 0, 0, 0, 0] 同樣，差分數組的大小是原數組大小加一。

2. 第一個區間 ([2, 4]) 的加值：

   • 在位置 2 上加 1：diff = [0, 0, 1, 0, 0, 0, 0]
   • 在位置 5 上減 1（位置 4 的下一個位置）：diff = [0, 0, 1, 0, 0, -1, 0]

3. 第二個區間 ([3, 5]) 的加值：

   • 在位置 3 上加 2：diff = [0, 0, 1, 2, 0, -1, 0]
   • 在位置 6 上減 2（位置 5 的下一個位置）：diff = [0, 0, 1, 2, 0, -1, -2]

4. 通過差分數組統計最終的 dur 數組：

   • 迴圈 diff 並更新 dur：
     • ( i = 1 )：dur[1] = 0。
     • ( i = 2 )：dur[2] = 1（累加得 1）。
     • ( i = 3 )：dur[3] = 3（累加得 1 + 2）。
     • ( i = 4 )：dur[4] = 3（累加得 3 + 0）。
     • ( i = 5 )：dur[5] = 2（累加得 3 - 1）。
     • ( i = 6 )：dur[6] = 0（累加得 2 - 2）。

結果

最終，dur 數組更新為：dur = [0, 0, 1, 3, 3, 2]

---

代碼實作

def main():
    n,m = map(int,input().split())
    dur = [0] * (n + 2)
    diff = [0] * (n + 2)

    for _ in range(m):
        l,r,w = map(int, input().split())
        diff[l] += w
        diff[r+1] -= w

    machine = [int(num) for num in input().split()]

    currect = 0

    for i in range(1 ,len(diff)):
        dur[i] = currect + diff[i]
        currect = dur[i]

    dur.pop(0)
    dur.pop()

    times = 0

    machine.sort(reverse=True)
    dur.sort()

    for i in range(len(dur)):
        times += dur[i] * machine[i]

    print(times)
    
if __name__ == "__main__":
    main()

本題知識

• 差分數組

• pop用法：[(這是陣列)].pop(位置)

  Ex:

  the_list = [0,1,2,3,4]
  the_list.pop(0) // output: [1,2,3,4]