有間企業最近新開了 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