B. Building Company The 13th Shandong ICPC Provincial Collegiate Programming Contest

B. Building Company The 13th Shandong ICPC Provincial Collegiate Programming Contest

Problem - B - Codeforces

题目大意：公司内有一些岗位，初始岗位ti由ui名员工担任，由n个项目，每个项目有m个需求岗位只要所有需求岗位就能完成这个工程，完成后有k个奖励，会有一些岗位的一些员工加入公司，问最多能完成几个工程

1<=n,m,k<=1e5;1<=t,u<=1e9

思路：如果我们逐个项目判断能否完成，那么时间复杂度将是n*m，那么我们可以判断每个岗位，将每个岗位在各项目中的所需员工数从小到大排序，每当这个岗位有新员工时，我们就判断哪些项目的该岗位需求能被满足，所以每个项目要维护一个当前限制数，初始等于m，每满足一个岗位的需求，限制数就-1，限制数为0就可以完成这个项目，用队列存储所有可以完成的项目，逐一领取奖励然后解除岗位限制即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
map<ll, ll>have;
map<ll, priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>>need;
int res[N];
vector<pair<ll, ll>>rew[N];
int main()
{cin.tie(0);ios::sync_with_stdio(false);int g;cin >> g;for (int i = 1; i <= g; i++){int x, y;cin >> x >> y;have[x] += y;//记录每个岗位有多少个员工可用}int q;cin >> q;queue<int>ava;int ans = 0;for (int i = 1; i <= q; i++){int m;cin >> m;for (int j = 1; j <= m; j++){ll x, y;cin >> x >> y;if (have[x] >= y){//初始就被满足的岗位不用管continue;}need[x].push({ y,i });//第i个项目岗位x需要y个人，按y从小到大排序res[i]++;//记录限制数}cin >> m;for (int j = 1; j <= m; j++){ll x, y;cin >> x >> y;rew[i].push_back({ x,y });//记录每个项目奖励的员工}if (!res[i]){ans++;//记录答案ava.push(i);//将限制都被满足的项目入队}}while (!pty()){int u = ava.front();ava.pop();for (int i = 0; i < rew[u].size(); i++){//对于能完成的项目直接领取奖励ll x = rew[u][i].first, y = rew[u][i].second;have[x] += y;while (!need[x].empty()){ll now = need[x].top().first;int id = need[x].top().second;if (have[x] >= now){//对于所有需要员工少于当前拥有员工的need[x].pop();res[id]--;//该项目限制数-1if (!res[id]){ans++;ava.push(id);}}else{break;}}}}cout << ans << endl;return 0;
}