d075. Q-6-10. 置物櫃出租 (APCS201810)

Content

王老先生有一個置物櫃，共有 $ M $ 個相同大小的格子，置物櫃目前已經租給 $ n $ 個客戶，第 $ i $ 位客戶所租的大小為 $ f(i)$ 個格子 $(1 ≤ i ≤ n)$ 。

目前的承租量總和不超過 $ M$ ，但是現在王老先生自己需要使用 $ S $ 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退，而退租第 $ i $ 個客戶損失的利益與其所租容量 $ f(i)$ 相同，

請寫一支程式計算王老先生最小的損失利益，如果不須退租，則損失為 $ 0$ 。

Input

測試資料有兩行，第一行有三個正整數，依序是 $ n$ 、 $M $ 與 $ S$ ，其中 $ S <= M$ ，

第二行是 $ n $ 個正整數 $ f(1)$ , $ f(2)$ , $ f(3)$ , $ ...$ , $ f(n)$ ，同一行的數字間以空白隔開，此行的最後有一個空格

如果你用了 python 的 splite(' ') 發生錯誤，那是因為行尾有空格，直接用 splite() 即可避免

$1 ≤ n ≤ 100$，$M ≤ 2e5$。

Output

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

Sample Input #1

3 10 6
4 4 1

Sample Output #1

Sample Input #2

5 20 14
8 2 7 2 1

Sample Output #2

測資資訊：

記憶體限制： 128 MB
公開測資點#0 (6%): 1.0s , <1K
公開測資點#1 (6%): 1.0s , <1K
公開測資點#2 (6%): 1.0s , <1K
公開測資點#3 (6%): 3.0s , <1K
公開測資點#4 (6%): 3.0s , <1K
公開測資點#5 (6%): 3.0s , <1K
公開測資點#6 (6%): 3.0s , <1K
公開測資點#7 (6%): 3.0s , <1K
公開測資點#8 (6%): 3.0s , <1K
公開測資點#9 (6%): 3.0s , <1K
公開測資點#10 (6%): 3.0s , <1K
公開測資點#11 (6%): 3.0s , <1K
公開測資點#12 (7%): 3.0s , <1K
公開測資點#13 (7%): 3.0s , <1K
公開測資點#14 (7%): 3.0s , <1K
公開測資點#15 (7%): 1.0s , <1K

Hint ：

Tags:

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

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