a202:
3. 生產線
內容
有 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
子題配分
- (30%): 1≤n,m≤100,w[i]=1
- (30%): w[i]=1
- (40%): 無額外限制
輸出說明
輸出最小的總花費時間
範例輸入
#1
5 1 2 4 1 1 2 3 4 5
範例輸出
#1
6
範例輸入
#2
10 3 2 5 6 3 6 4 7 8 1 1 2 3 4 5 6 7 8 9 10
範例輸出
#2
117
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 0.5s , <1K
公開 測資點#2 (5%): 0.5s , <1M
公開 測資點#3 (5%): 0.5s , <1M
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <10M
公開 測資點#7 (5%): 0.5s , <10M
公開 測資點#8 (5%): 0.5s , <10M
公開 測資點#9 (5%): 0.5s , <10M
公開 測資點#10 (5%): 0.5s , <10M
公開 測資點#11 (5%): 0.5s , <10M
公開 測資點#12 (5%): 0.5s , <10M
公開 測資點#13 (5%): 0.5s , <10M
公開 測資點#14 (5%): 0.5s , <10M
公開 測資點#15 (5%): 0.5s , <10M
公開 測資點#16 (5%): 0.5s , <10M
公開 測資點#17 (5%): 0.5s , <10M
公開 測資點#18 (5%): 0.5s , <10M
公開 測資點#19 (5%): 0.5s , <10M
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 0.5s , <1K
公開 測資點#2 (5%): 0.5s , <1M
公開 測資點#3 (5%): 0.5s , <1M
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <10M
公開 測資點#7 (5%): 0.5s , <10M
公開 測資點#8 (5%): 0.5s , <10M
公開 測資點#9 (5%): 0.5s , <10M
公開 測資點#10 (5%): 0.5s , <10M
公開 測資點#11 (5%): 0.5s , <10M
公開 測資點#12 (5%): 0.5s , <10M
公開 測資點#13 (5%): 0.5s , <10M
公開 測資點#14 (5%): 0.5s , <10M
公開 測資點#15 (5%): 0.5s , <10M
公開 測資點#16 (5%): 0.5s , <10M
公開 測資點#17 (5%): 0.5s , <10M
公開 測資點#18 (5%): 0.5s , <10M
公開 測資點#19 (5%): 0.5s , <10M
提示 ：
標籤:
出處:
2021年11月APCScthbst (吳宗達)
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||