g421. PC.分身五河 - 高中生程式解題系統

內容

一年一度(?的情人節又到了。為了應付每個精靈提出的約會請求，拉塔托斯克研發出了類似刻刻帝Zaphkiel八之彈能力的裝置，讓士道可以透過召喚過去時間點中的自己，來達到分身的效果。

已知裝置可以製造出$K-1$個分身，加上本體一共有$K$個士道

共有$N$個精靈提出約會請求，而精靈們所要求的約會時間分別為 $T_1 \sim T_N$

請問共要多少時間才能讓所有精靈約會完?

*士道會按照約會請求表的順序來安排與精靈的約會*

對了，這是我婆↓↓ by哈哈是Kai啦

輸入說明

給定兩個正整數 $N,K$，$1 \le N,K \le 10^6$，代表有N個人要約會，以及有K個士道。

緊接著，有 $N$ 個數字，$T_1$,...,$T_N$，代表排在第$i$ 個的人約會所需的時間。

輸出說明

請輸出要花多少時間，才能讓所有精靈都約會完？

範例輸入 #1

3 2
3 5 2

範例輸出 #1

範例輸入 #2

3 1
1 2 3

範例輸出 #2

範例輸入 #3

3 5
1 3 7

範例輸出 #3

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (10%): 2.0s , <1K
不公開測資點#1 (10%): 2.0s , <1K
不公開測資點#2 (10%): 2.0s , <10M
不公開測資點#3 (57%): 2.0s , <1M
不公開測資點#4 (13%): 2.0s , <10M

提示：

範測1:

在第0分鐘時兩個士道分別約會3分鐘跟5分鐘

在第3分鐘時，其中一個士道約會結束，繼續去跟兩分鐘的約會

在第5分鐘時，所有士道結束他們的約會

輸出5為答案

10% 的測試資料滿足 $1\leq N,K \leq 3$ 而且$ 0 \leq T_i \leq 1 $

10% 的測試資料滿足 $1 \leq N \leq K \leq 10$ 而且 $0 \leq T_i \leq 10^5 $

10% 的測試資料滿足 $1 \leq N,K \leq 10^6$ 而且 $0 \leq T_i \leq 1 $

57% 的測試資料滿足 $1 \leq N,K \leq 10^6$ 而且 $0 \leq T_i \leq 10^5 $

13% 的測試資料滿足 $1 \leq N,K \leq 10^6$ 而且 $0 \leq T_i \leq 10^9 $

題目-Kai

狂三我婆，不服來戰

標籤:

出處:

[管理者： kaihsinchen2 (Kai-Hsin Chen 2) ]