ZeroJudge J537: 工廠派遣 (Factory)

有間企業最近新開了 N 間工廠,打算將員工派遣至各工廠工作。各工廠有預估的營收值 Ai 和員工需求人數 P。i 企業主將依據工廠的營收值由高到低來分配員工若營收值較高的工廠已滿足員工需求人數,才會將員工分配給營收值較低的工廠直到所有員工都已分配完成或者所有工廠的需求都已滿足為止

假設不會有任兩間工廠的預估營收值相同。給定各工廠的資訊以及企業的總員工數,請你撰寫程式計算有幾間工廠有員工進駐。

範例測資

範例輸入範例輸出
輸入第一列有一個整數 N (1 ≤ N ≤ 350),代表有幾間工廠。接下來有 N 列,每列有兩個整數 Ai (1≤ Ai ≤ 6000,i = 1, 2, 3, …, N) 和 Pi (1 ≤ Pi ≤ 3000,i = 1, 2, 3, …, N),代表的是第 i 間工廠的預估營收值及員工需求人數。
最後一列有一個整數 H (0 ≤ H ≤ 1,050,000),代表總員工數。
請根據工廠派遣規則,輸出有幾間工廠有員工進駐
3
30 10
20 5
10 3
10
1
4
2 6
3 2
5 7
8 9
18
3
6
90 5
30 6
70 8
20 4
1000 5000
500 800
5130
2

解題思路

使用 Pair<int, int> 將每個工廠的「預期營收值」和「需要的人數」存在一起,並將每一個工廠的 Pair 存到陣列中進行 Sort,最後面的 Pair 就會是「預期營收值最大的工廠」。

使用 For迴圈 從最後面跑到最前面的位置,每一次將 H 減掉目前工廠「需要的人數」並將答案變數 +1。每次 For迴圈 都需要判斷 H 是否小於等於 0,如果是的話就可以將 For 迴圈 Break掉。

範例程式碼-ZeroJudge J537: 工廠派遣 (Factory)

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

pair<int, int> rtn (int a, int b)
{
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    vector<pair<int, int>>v;
    for (int i = 0; i<N; i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back(rtn(a, b));
    }
    sort(v.begin(), v.end());
    int count;
    cin >> count;
    int ans = 0;
    for (int i = N-1; i>=0; i--)
    {
        if (count <= 0) break;
        count -= v[i].second;
        ans++;
    }
    cout << ans << "\n";
}

//ZeroJudge J537
//Dr. SeanXD

發佈留言