ZeroJudge 解題筆記：j537. 工廠派遣 (Factory)

作者：王一哲
日期：2025年4月17日



ZeroJudge 題目連結：j537. 工廠派遣 (Factory)

解題想法

這題將每間工廠的産值 a、需要的人數 p，綁在一起放入陣列，依照 v 由大到小排序會比較方便。

Python 程式碼

使用時間約為 21 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # n 間工廠
    # 讀取每間工廠的産值 a、需要的人數 p，組成 tuple、放入 list，依照 v 由大到小排序
    ap = sorted([tuple(map(int, input().split())) for _ in range(n)], reverse=True)
    h = int(input())  # 總人數
    cnt = 0  # 有分配到人的工廠數量
    idx = 0  # 從 ap 讀取資料的索引值
    while idx < n and h > 0:  # 如果 idx 還沒有出界而且還有人，繼續執行
        cnt += 1; h -= ap[idx][1]; idx += 1  # cnt 加 1，h 減去此工廠的人數，idx 加 1
    print(cnt)

C++ 程式碼

使用時間約為 3 ms，記憶體約為 356 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // n 間工廠
    while(cin >> n) {
        // 讀取每間工廠的産值 a、需要的人數 p，放入 array，依照 v 由大到小排序
        vector<pair<int, int>> ap (n);
        for(int i=0; i<n; i++) {
            int a, p; cin >> a >> p;
            ap[i] = make_pair(a, p);
        }
        sort(ap.begin(), ap.end(), greater<pair<int, int>> ());
        int h; cin >> h;  // 總人數
        int cnt = 0, idx = 0;  // 有分配到人的工廠數量，從 ap 讀取資料的索引值
        while(idx < n && h > 0) {  // 如果 idx 還沒有出界而且還有人，繼續執行
            cnt++; h -= ap[idx].second; idx++;  // cnt 加 1，h 減去此工廠的人數，idx 加 1
        }
        cout << cnt << "\n";
    }
    return 0;
}