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

相關文章

發佈留言