APCS202111 第3題生產線

上傳作業：http://203.68.236.9/problem/c0202

zerojudge網址  https://zerojudge.tw/ShowProblem?problemid=g597

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

輸入說明

先輸入兩個正整數 n 和 m 代表有 n 台機器和 m 個工作 接下來有 m 行, 每行有三個正整數 l[i], r[i] 和 w[i] 代表第 i 個工作需要編號從 l[i] 到 r[i] 的機器完成, 並且需要各產生出 w[i] 單位的資料 最後一行包含 n 個正整數 t[1],t[2],⋯t[n] 

數字範圍 

1≤n,m≤200000 

1≤w[i]≤100 

1≤t[i]≤100 

1≤l[i]≤r[i]≤n

輸出說明

輸出最小的總花費時間

輸入範例

5 1

2 4 1

1 2 3 4 5

10 3

2 5 6

3 6 4

7 8 1

1 2 3 4 5 6 7 8 9 10

輸出範例

6

117

解題策略

差分、排序、貪婪

第一組測資

5 1

2 4 1

1 2 3 4 5

生產資料量  1 1 1

時間           1 2 3 4 5

機器              1 2 3

          1*1+1*2+1*3=6

第二組測資

10 3

2 5 6

3 6 4

7 8 1

1 2 3 4 5 6 7 8 9 10

生產資料量     6 10 10 10  4  1  1

時間             1 2  3   4   5   6   7  8

機器                 4 1   2    3   5  6  7

          10*1 + 10*2 + 10*3 + 6*4 + 4*5 + 1*6 + 1*7 =117

使用差分與累加計算每一個時間點的生產資料量，生產資料量最大的時間點安排t[i]最小的機器，將生產資料量由大到小排序，t[i]由小到大排序，依序相乘累加。