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


Submit solution

Points: 100 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem type

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

輸入格式

測試資料有兩行,第一行有三個正整數,依序是 \( n\) 、 \(M \) 與 \( S\) ,其中 \( S <= M\) , 第二行是 \( n \) 個正整數 \( f(1)\) , \( f(2)\) , \( f(3)\) , \( ...\) , \( f(n)\) ,同一行的數字間以空白隔開,此行的最後有一個空格 如果你用了 python 的 splite(' ') 發生錯誤,那是因為行尾有空格,直接用 splite() 即可避免   \(1 ≤ n ≤ 100\),\(M ≤ 2e5\)。

輸出格式

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

範例輸入 1

3 10 6
4 4 1

範例輸出 1

5

範例輸入 2

5 20 14
8 2 7 2 1

範例輸出 2

15

Comments

There are no comments at the moment.