d050: Q_4_8 先到先服務 (*
Tags : ch4
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-06 12:50

Content

 有 n 個客人要分配到 m 個櫃台來服務,客人依編號順序到達,第 i 個客人需要 t(i) 的時間來完成(無論分配到哪一個櫃台),而且每個客人的需求必須在同一個櫃台完 成。因為公平的因素,先到客人不可以比晚到客人更晚開始服務。現在希望安排每個 客人的服務櫃檯,以便可以在最短的時間內完成所有客人的需求。舉例來說,如果有三位客人與兩個櫃台,需求的時間依序是(3,1,5),我們可以如下 圖分配,最後的完成時間是 6。

請注意,我們不可以如下分配,雖然這樣的完成時間會減少到 5,但是第 3 個客人比 第 2 個客人早開始服務違反了先到先服務的原則。

Input

 輸入兩行,第一行是正整數 n 與 m,第二行是 n 個正整數 t(1), t(2),…,t(n),同行數字間以空白間格。n 與 m 不超過 2e5,t(i)不超過 1e4。

Output

 最早可能服務完所有客人的時間。

Sample Input #1
3 2
3 1 5
Sample Output #1
6
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
ch4
出處:
Dr.Wu [管理者:
ktlai@cmgsh.... (好冷阿)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」