e094. Q-6-10. 置物櫃出租 (APCS201810) - 花中程式設計挑戰系統

Content

王老先生有一個置物櫃，共有 M 個相同大小的格子，置物櫃目前已經租給 n 個客戶，第 i 位客戶所租的大小為 f(i)個格子(1 <= i <= n)。目前的承租量總和不超過 M，但是現在王老先生自己需要使用 S 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退，而退租第 i 個客戶損失的利益與其所租容量 f(i)相同，請寫一支程式計算王老先生最小的損失利益，如果不須退租，則損失為 0。

Time limit: 1 秒

Input

測試資料有兩行，第一行有三個正整數，依序是 n、M 與 S，其中 S <= M，第二行是 n 個正整數 f(1), f(2), f(3), ..., f(n)，同一行的數字間以空白隔開。1 <= n <= 100，M <= 2e5

Output

輸出王老先生最小的損失利益。

Sample Input

Sample Output

範例一：
5

範例二：
15

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

Hint ：

範例一說明：總共容量 10，已出租 9，剩下 1，需要 6，最少退租 4+1=5。

範例二說明：總共容量 20，已出租 20，剩下 0，需要 14，最少退租 8+7=15。

Tags:

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

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