e465. 置物櫃分配
標籤 : DP 背包
通過比率 : 237人/364人 ( 65% ) [非即時]
評分方式:
Tolerant

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

內容

你是個櫃子租借商,總共擁有 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 個櫃子。

輸入說明

第一行有三個正整數 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

輸出說明

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

範例輸入 #1
20 14 5
1 7 2 8 2
範例輸出 #1
15
測資資訊:
記憶體限制: 64 MB
提示 :
標籤:
DP 背包
出處:
2018年10月APCS [管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
42982 lbm00138 (bits/stdc++.h) e465
61 2024-10-14 00:15
41594 seancai78@gm ... (風月春秋) e465
set解法思路
150 2024-08-09 01:50
40041 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) e465
446 2024-04-24 11:19
37909 s11104220@sc ... (施同學) e465
我的思路
546 2023-10-17 20:48
37792 edoctopus322 ... (Moon Jam) e465
718 2023-10-08 15:32