a214. Q_6_10 置物櫃出租 (APCS201810)
Tags : ch6
Accepted rate : 22人/23人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-04-12 19:49

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 2e5$

Output

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

Sample Input #1
3 10 6
4 4 1
Sample Output #1
5
Sample Input #2
5 20 14
8 2 7 2 1
Sample Output #2
15
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (14%): 1.0s , <1K
公開 測資點#1 (14%): 1.0s , <1K
公開 測資點#2 (14%): 1.0s , <1K
公開 測資點#3 (14%): 1.0s , <1K
公開 測資點#4 (14%): 1.0s , <1K
公開 測資點#5 (15%): 1.0s , <1K
公開 測資點#6 (15%): 1.0s , <1K
Hint :
Tags:
ch6
出處:
Prof.Wu [管理者: zero(管理員) ]


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