上傳作業：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]由小到大排序，依序相乘累加。