APCS 置物櫃分配 (zerojudge e465)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 392 所需閱讀時間 ≈ 1 分鐘

題目網址

你是個櫃子租借商，總共擁有 M 個櫃子。 現在這 M 個櫃子分別被 N 個人借用，借用量分別為 (x0, x1, x2, …xN-1) 個櫃子， 其中 x0 + x1 + x2 + … + xN-1 ≤ M

現在你想要使用 S 個空櫃子， 在被借用的櫃子只能夠 全退 或 全不退之下，最少需要請這 N 個人退還多少櫃子？ 也就是當有一個人借用 10 個櫃子時，不能夠只請他退還 5 個櫃子。

解題思路： 這題我的做法是先整理出哪些櫃子數量可以由數個 x 相加而成，然後再找大於等於需要櫃子量的最小值，不過這樣依照題目給定的 N、M 範圍應該是過不了的，在最糟狀況下會是 \(O(N^2+M)\)，只是試了之後是可以 AC 的，後來看別人的解法是用 01 背包問題解，但也會到 \(O(MN)\)，如果是這樣的範圍應該要比較像中一中 judge 上的這題，不過輸入順序不同，需要稍微修改。

🌟題目給的 S 是需要的空櫃子，但事實上那些人要給你的數量只有 S-(M-total_x)，total_x 表示所有 x 的和，也就是說，如果 S-(M-total_x) 是負的，那就代表你不需要請人退櫃子，因為你已經有足夠的空櫃子了，而當正的時候，就是你需要請人退櫃子的數量。

APCS 置物櫃分配 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

int n, m, s, total_x=0, x[100005];
bool add[100005];
vector<int> add_history;
//add[i] 表示x陣列是否能任意選取使得加總為i
//將題目轉換判斷x陣列是否能任意選取使得加總為k，再遍歷整個陣列找大於等於需要量的最小值

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(add,0,sizeof(add));
    cin>> m>> s >> n;
    for(int i = 0; i<n; i++) cin >> x[i], total_x+=x[i];
    add_history.push_back(0), add[0]=1;
    for(int i = n-1;i>=0;i--){
        vector<int> new_history;
        for(int num : add_history){
            int cur = num+x[i];
            if(!add[cur]) add[cur]=1, new_history.push_back(cur);
        }for(int num : new_history) add_history.push_back(num),add[num]=1;
    }

    s -= (m-total_x); //s表示還需要的櫃子數量
    if(s<=0){
        cout << 0 << '\n';
    }else{
        for(int i = s;i<=total_x; i++)
            if(add[i]){
                cout << i << '\n'; break;
            }
    }

    return 0;
}

AC的Submission～ 中一中judge AC的Submission～