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
Use the 0/1 knapsack concept to handle the data. First, determine how much space still needs to be freed up. There may be cases where no space needs to be freed, and the answer is directly 0. The answer is the first number that has a solution after reaching or exceeding 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