ZeroJudge J537: Factory

A company recently opened N factories and plans to assign employees to each factory. Each factory has an estimated revenue value Ai and a required number of employees Pi. The company owner will assign employees to factories based on the revenue values in descending order. If a factory with a higher revenue value has already met its employee requirement, employees will be assigned to the factory with the next highest revenue value, until all employees are assigned or the requirements of all factories are met.

Assume that no two factories have the same estimated revenue value. Given the information for each factory and the total number of employees in the company, please write a program to calculate how many factories have employees assigned to them.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line of input contains an integer N (1 ≤ N ≤ 350), representing the number of factories. The next N lines each contain two integers Ai (1 ≤ Ai ≤ 6000, i = 1, 2, 3, …, N) and Pi (1 ≤ Pi ≤ 3000, i = 1, 2, 3, …, N), representing the estimated revenue and the number of employees required for the i-th factory. The last line contains an integer H (0 ≤ H ≤ 1,050,000), representing the total number of employees.According to the factory assignment rules, output how many factories have employees assigned.
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

Thought Process

Use a Pair to store each factory's "expected revenue" and "required number of employees" together, and store each factory's Pair in an array for sorting. The Pair at the end of the array will be the factory with the "highest expected revenue".

Use a For loop to iterate from the end to the beginning of the array. Each time, subtract the current factory's "required number of employees" from H and increment the answer variable by 1. In each iteration of the For loop, check if H is less than or equal to 0, and if so, break out of the For loop.

Sample Code－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
Tags

Related Posts

Comments