e064. Q-4-8. 先到先服務 (*) - 花中程式設計挑戰系統

Content

有 n 個客人要分配到 m 個櫃台來服務，客人依編號順序到達，第 i 個客人需要 t(i) 的時間來完成(無論分配到哪一個櫃台)，而且每個客人的需求必須在同一個櫃台完成。因為公平的因素，先到客人不可以比晚到客人更晚開始服務。現在希望安排每個客人的服務櫃檯，以便可以在最短的時間內完成所有客人的需求。

舉例來說，如果有三位客人與兩個櫃台，需求的時間依序是(3,1,5)，我們可以如下圖分配，最後的完成時間是 6。

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

Time limit: 1 秒

Input

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

Output

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

Sample Input

3 2
3 1 5

Sample Output

測資資訊：

記憶體限制： 64 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:

greedy 排序

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

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