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

最近更新 : 2023-12-20 21:39

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%): 3.0s , <1K
公開 測資點#11 (5%): 3.0s , <1K
公開 測資點#12 (5%): 3.0s , <1K
公開 測資點#13 (5%): 3.0s , <1K
公開 測資點#14 (5%): 3.0s , <1K
公開 測資點#15 (5%): 3.0s , <1K
公開 測資點#16 (5%): 3.0s , <1K
公開 測資點#17 (5%): 3.0s , <1K
公開 測資點#18 (5%): 3.0s , <1K
公開 測資點#19 (5%): 3.0s , <1K
Hint :
Tags:
DP 背包
出處:
2018年10月APCS [管理者: mushroom.cs9 ... (mushroom) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
37909 s11104220@sc ... (施同學) e465
我的思路
181 2023-10-17 20:48
37792 edoctopus322 ... (Moon Jam) e465
231 2023-10-08 15:32
35780 asnewchien@g ... (david) e465
355 2023-06-16 15:59