e465. 置物櫃分配
Tags : DP 背包
Accepted rate : 49人/76人 ( 64% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-06 01:36

Content

你是個櫃子租借商,總共擁有 M 個櫃子。
現在這 M 個櫃子分別被 N 個人借用,借用量分別為 (x0, x1, x2, ...xN-1) 個櫃子,
其中 x0 + x+ x2 + ... + xN-1 ≤ M

現在你想要使用 S 個空櫃子,
在被借用的櫃子只能夠 全退 或 全不退之下,最少需要請這 N 個人退還多少櫃子?
也就是當有一個人借用 10 個櫃子時,不能夠只請他退還 5 個櫃子。

舉例來說,對於 M =  20 個櫃子,
現在分別被 5 個人借用 (1, 7, 2, 8, 2) 個櫃子,

在需要使用 S = 14 個櫃子之下,
最少需要請他們退還 7 + 8 = 15 個櫃子。

Input

第一行有三個正整數 M、S、N,
分別代表櫃子總數 M 、 想要使用的櫃子數 S 、 借用人數 N。
M ≤ 100,000
S ≤ M
N ≤ 100,000

第二行有 N 個非負整數 x0, x1, x2, ...xN-1
代表每個人所借用的櫃子數量。
其中 x0 + x+ x2 + ... + xN-1 ≤ M

Output

最少需要請這 N 個人退還的櫃子總數

Sample Input #1
20 14 5
1 7 2 8 2
Sample Output #1
15
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
Hint :
Tags:
DP 背包
出處:
2018年10月APCS [管理者: mushroom.cs9...(mushroom) ]


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