d079. Q_6_10 置物櫃出租 (APCS201810)

Content

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

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

Input

測試資料有兩行，

第一行有三個正整數，依序是 $n$ 、$M$ 與 $S$ ，其中$S \leq M$，
第二行是n個正整數 $f_1, f_2, f_3, ..., f_n$，同一行的數字間以空白隔開。

$1 \leq n \leq 100$ ， $M \leq 2 \times 10^5$

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

測資資訊：

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

Hint ：

Tags:

ch6

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

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