Try   HackMD

APCS實作題2018年：置物櫃分配

第1版：2023年9月9日
第2版：2024年12月21日
作者：王一哲
題目來源：107年6月實作題
ZeroJudge 題目連結


題目

問題描述

你是個櫃子租借商，總共擁有

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≤100000,     S≤M,     N≤100000

第二行有

N 個非負整數
x0,x1,x2,…,xN−1，代表每個人所借用的櫃子數量。
其中
x0+x1+x2+⋯+xN−1≤M。

輸出格式

最少需要請這

N 個人退還的櫃子總數

範例：輸入

20 14 5
1 7 2 8 2

範例：正確輸出

15

Python 程式碼

寫法1，使用 bitset

以下的程式碼主要參考這個網頁，使用 bitset 求指定資料可能的總合主要參考 LeetCode 416. Partition Equal Subset Sum 討論區 C++ Bitset Solution。其中最難理解的部分是第3、4行，以 ZeroJudge 網頁的範例來說明，由於已借出的格子數為

1,7,2,8,2，可能的總合有
1,2,3,4,5,7,8,9,10,11,12,13,15,16,17,18,19,20，如果 possSum 先設定為1，先將 possSum 向左移1位再與原本的值取 or 運算，其2進位值為

0b11

這代表 possSum 可能為 1。接下來再向左平移7位並與原本的值取 or 運算，其2進位值為

0b110000011

這代表 possSum 可能為 1、7、8，也就是看2進位值中哪幾個位數是1，就代表總合可能是這幾個位數。接下再代入 2、8、2 的結果依序為

0b11110001111
0b1111000111110001111
0b111111011111110111111

再由最後一位向前搜尋字串1，如果 target 對應的位數不是1，再繼續向前找，找到的位數就是答案。

於 ZeroJudge 測試結果，最長運算時間約為 44 ms，使用記憶體最多約為 3.5 MB，通過測試。



















def solve(array, tar):
    possSum = 1
    for x in array:
        possSum |= (possSum << x)
    s = bin(possSum)[2:]
    for i in range(len(s)):
        if i >= tar and s[len(s)-i-1] == '1':
            return i

M, S, N = map(int, input().split())
data = list(map(int, input().split()))
left = M - sum(data)  # 目前剩下的空格數
target = S - left     # 需要歸還的格子數量

if target <= 0:       # 如果 target <= 0 不需要歸還格子，印出0
    print(0)
else:
    print(solve(data, target))

寫法2，使用二維陣列及 DP

於 ZeroJudge 測試結果，有6筆測資需要的記憶體爆掉。


















M, S, N = map(int, input().split())  # M 個櫃子，需要 S 個櫃子，有 N 個人借用
xs = list(map(int, input().split()))  # 每個客戶租用的格子數量
ans = M  # 答案預設為 M
goal = S - (M - sum(xs))  # 目標需要收回的格子數量
if goal <= 0: ans = 0  # 不需要歸還任何櫃子，答案為 0
else:  # 需要歸還櫃子
    dp = [[0]*(M+1) for _ in range(N+1)]  # dp[i][j] 為第 i 個客戶累計收回 j 個格子
    if xs[0] >= goal: ans = min(ans, xs[0])  # 更新 ans，取較小的值
    for j in range(xs[0], M+1): dp[1][j] = xs[0]  # 處理第 1 項
    for i, x in enumerate(xs[1:], start=2):  # 處理第 2 ~ n 項
        for j in range(1, M+1):  # 依序檢查收回格子數量 1 ~ M
            if x > j: dp[i][j] = dp[i-1][j]  # 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
            else:  # 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-x] + x)
                if dp[i][j] >= goal: ans = min(ans, dp[i][j])  # 大於等於目標，更新 ans，取較小的值

print(ans)

寫法3，使用滾動陣列及 DP

於 ZeroJudge 測試結果，最後一筆測資超時。



















M, S, N = map(int, input().split())  # M 個櫃子，需要 S 個櫃子，有 N 個人借用
xs = list(map(int, input().split()))  # 每個客戶租用的格子數量
ans = M  # 答案預設為 M
goal = S - (M - sum(xs))  # 目標需要收回的格子數量
if goal <= 0: ans = 0  # 不需要歸還任何櫃子，答案為 0
else:  # 需要歸還櫃子
    d, p = [0]*(M+1), [0]*(M+1)  # 為第 i 個客戶累計收回 j 個格子
    if xs[0] >= goal: ans = min(ans, xs[0])  # 更新 ans，取較小的值
    for j in range(xs[0], M+1): p[j] = xs[0]  # 處理第 1 項
    for x in xs[1:]:  # 處理第 2 ~ n 項
        for j in range(1, M+1):  # 依序檢查收回格子數量 1 ~ M
            if x > j: d[j] = p[j]  # 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
            else:  # 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                d[j] = max(p[j], p[j-x] + x)
                if d[j] >= goal: ans = min(ans, d[j])  # 大於等於目標，更新 ans，取較小的值
        d, p = p, d  # 交換資料

print(ans)



C++ 程式碼

寫法1，使用 bitset

於 ZeroJudge 測試結果，最長運算時間約為 7 ms，使用記憶體最多約為 704 kB，通過測試。




































#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

int solve(vector<int> array, int tar);

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int M, S, N; cin >> M >> S >> N;
    vector<int> data (N, 0);
    int total = 0;
    for(int i=0; i<N; i++) {
        cin >> data[i];
        total += data[i];
    }
    int left = M - total;  // 目前剩下的空格數
    int target = S - left; // 需要歸還的格子數量
    if (target <= 0)       // 如果 target <= 0 不需要歸還格子，印出0
        cout << 0 << "\n";
    else
        cout << solve(data, target) << "\n";
    return 0;
}

int solve(vector<int> array, int tar) {
    bitset<1000000> possSum;
    possSum[0] = 1;
    for(auto x : array) 
        possSum |= (possSum << x);
    for(int i=tar; i<1000000; i++) {
        if (possSum[i] == 1) return i;
    }
    return 0;
}

寫法2，使用二維陣列及 DP

於 ZeroJudge 測試結果，最長運算時間約為 39 ms，使用記憶體最多約為 39.4 MB，通過測試。

































#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int M, S, N, isum = 0; cin >> M >> S >> N;  // M 個櫃子，需要 S 個櫃子，有 N 個人借用
    vector<int> xs (N, 0);  // 每個客戶租用的格子數量
    for(int i=0, x; i<N; i++) {
        cin >> x; xs[i] = x; isum += x;  // isum 為已出借的櫃子數量
    }
    int ans = M, goal = S - (M - isum);  // 答案預設為 M，目標需要收回的格子數量
    if (goal <= 0) ans = 0;  // 不需要歸還任何櫃子，答案為 0
    else {  // 需要歸還櫃子
        vector<vector<int>> dp (N+1, vector<int> (M+1, 0));  // dp[i][j] 為第 i 個客戶累計收回 j 個格子
        if (xs[0] >= goal) ans = min(ans, xs[0]);  // 更新 ans，取較小的值
        for(int j=xs[0]; j<=M; j++) dp[1][j] = xs[0];  // 處理第 1 項
        for(int i=2; i<=N; i++) {  // 處理第 2 ~ n 項
            for(int j=1, x; j<=M; j++) {  // 依序檢查收回格子數量 1 ~ M
                x = xs[i-1];  // 目前在檢查的格子數量
                if (x > j) dp[i][j] = dp[i-1][j];  // 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
                else {  // 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-x] + x);
                    if (dp[i][j] >= goal) ans = min(ans, dp[i][j]);  // 大於等於目標，更新 ans，取較小的值
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

寫法3，使用滾動陣列及 DP

於 ZeroJudge 測試結果，最長運算時間約為 17 ms，使用記憶體最多約為 1.1 MB，通過測試。


































#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int M, S, N, isum = 0; cin >> M >> S >> N;  // M 個櫃子，需要 S 個櫃子，有 N 個人借用
    vector<int> xs (N, 0);  // 每個客戶租用的格子數量
    for(int i=0, x; i<N; i++) {
        cin >> x; xs[i] = x; isum += x;  // isum 為已出借的櫃子數量
    }
    int ans = M, goal = S - (M - isum);  // 答案預設為 M，目標需要收回的格子數量
    if (goal <= 0) ans = 0;  // 不需要歸還任何櫃子，答案為 0
    else {  // 需要歸還櫃子
        vector<int> d (M+1, 0), p (M+1, 0);  // 為第 i 個客戶累計收回 j 個格子
        if (xs[0] >= goal) ans = min(ans, xs[0]);  // 更新 ans，取較小的值
        for(int j=xs[0]; j<=M; j++) p[j] = xs[0];  // 處理第 1 項
        for(int i=2; i<=N; i++) {  // 處理第 2 ~ n 項
            for(int j=1, x; j<=M; j++) {  // 依序檢查收回格子數量 1 ~ M
                x = xs[i-1];  // 目前在檢查的格子數量
                if (x > j) d[j] = p[j];  // 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
                else {  // 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                    d[j] = max(p[j], p[j-x] + x);
                    if (d[j] >= goal) ans = min(ans, d[j]);  // 大於等於目標，更新 ans，取較小的值
                }
            }
            swap(d, p);  // 交換資料
        }
    }
    cout << ans << "\n";
    return 0;
}



tags:APCS、Python、C++
Last changed by 
 
Yi-Zhe Wang
0
323

Read more

中和高中「程式設計競賽與檢定」培訓講義

作者：王一哲 日期：2025年5月11日

May 24, 2025
Python 及 C++ 集合 (set)

作者：王一哲日期：2023年8月12日

May 24, 2025
Python 字典 (dictionary) 及 C++ STL map

作者：王一哲日期：2023年8月7日

May 23, 2025
APCS實作題2016年10月第1題：三角形辨別

第1版：2023年2月10日第2版：2023年6月5日，新增 C++ 程式碼以及不使用 sort 的寫法作者：王一哲題目來源：105年10月29日實作題第1題ZeroJudge 題目連結

May 16, 2025
Read more from Yi-Zhe Wang
Published on HackMD