ZeroJudge E465: 置物櫃分配

你是個櫃子租借商，總共擁有 M 個櫃子。
現在這 M 個櫃子分別被 N 個人借用，借用量分別為 (x0, x1, x2, …xN-1) 個櫃子，
其中 x0 + x1 + 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 + x1 + x2 + … + xN-1 ≤ M		最少需要請這 N 個人退還的櫃子總數
20 14 5
1 7 2 8 2		15

解題思路

使用 01 背包的概念來處理資料，需要先確認還需要騰出多少空間來，會有不需要騰空間直接輸出 0 的情況。答案就是 >= S 之後第一個有解的數字。

範例程式碼－ZeroJudge E465: 置物櫃分配

#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
標籤

相關文章

發佈留言