ZeroJudge J537: 工廠派遣 (Factory)

題目敘述

每筆測資第一行有一個正整數N，接下來會有N行，每行會有兩個正整數，分別代表預期營收值和需要的人數。最後一行有一個正整數代表總共配發幾個人，會從預期營收值最高的工廠開始配發人力，當最高預期營收值的工廠的人數滿足其需求之後才會開始配發次高預期營收值的工廠，以此類推。要求輸出這些人力總共配發至幾個工廠。

範例輸入 #1

3

30 10

20 5

10 3

10

範例輸出 #1

1

範例輸入 #2

4

2 6

3 2

5 7

8 9

18

範例輸出 #2

3

範例輸入 #3

6

90 5

30 6

70 8

20 4

1000 5000

500 800

5130

範例輸出 #3

2

解題思路

使用Pair將預期營收值和需要的人數存在一起，收完之後將這個Pair排序，最後面的資料就會是預期營收值最高的工廠。跑一個由大到小的For迴圈，並且每一次都將有的人數減到目前工廠所需的人數，並且建立一個存答案的變數+1。如果人數小於等於0，就Break掉For迴圈並輸出答案。

解題程式碼如下 (僅供參考)：

#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";
}