You are a locker rental provider with a total of M lockers. These M lockers are rented out by N people, with the number of lockers rented by each person represented as (x_0, x_1, x_2, \dots, x_{N-1}), where x_0 + x_1 + x_2 + \dots + x_{N-1} \leq M.
Now, you want to use S empty lockers. Under the condition that a rented locker can only be fully returned or not returned at all, how many lockers must be returned by these N people at a minimum? In other words, if a person rents 10 lockers, you cannot ask them to return only 5; they must return all 10 lockers.
For example, given M = 20 lockers, currently rented by 5 people with the rental amounts (1, 7, 2, 8, 2) :
If you need to use S = 14 lockers, the minimum number of lockers you need to ask them to return is 7 + 8 = 15 lockers.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains three positive integers M, S, and N, which represent the total number of lockers M, the number of lockers you want to use S, and the number of people N, respectively. • M \leq 100,000 • S \leq M • N \leq 100,000 The second line contains N non-negative integers x_0, x_1, x_2, \dots, x_{N-1}, which represent the number of lockers rented by each person. • It is guaranteed that x_0 + x_1 + x_2 + \dots + x_{N-1} \leq M . | The goal is to find the minimum total number of lockers that need to be returned by these N people in order to free up at least S lockers. |
| 20 14 5 1 7 2 8 2 | 15 |
Thought Process
使用 01 背包的概念來處理資料，需要先確認還需要騰出多少空間來，會有不需要騰空間直接輸出 0 的情況。答案就是 >= S 之後第一個有解的數字。
Sample Code－ZeroJudge E465: Locker Allocation
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int M, S, N, cabinet[100000] = {}, sum = 0;
cin >> M >> S >> N;
for (int i = 0; i < N; i++) {
cin >> cabinet[i];
sum += cabinet[i];
}
const int target = S - (M - sum);
if (target <= 0) cout << "0\n";
else {
map<int, int>MAP;
for (int i = 0; i<N; i++) {
const int item = cabinet[i];
for (int j = target; j>=0; j--) {
if (MAP[j] > 0) {
MAP[j + item]++;
}
}
MAP[item]++;
}
for (auto it:MAP) {
if (it.first >= target && it.second > 0) {
cout << it.first << "\n";
break;
}
}
}
}
//ZeroJudge E465
//Dr. SeanXD