POJ-3614 Sunscreen 题解

题目大意

每个人有一个最大SPF值，和一个最大SPF值，每个物品能够提供$SPF_i$给n个人，问最多能够满足多少个人。

解题思路

刚开始想的是贪心，优先给区间大小最小的值，同时用优先队列维护物品的数量。

然后wa吐了。

后面看了题解，发现是思路不对。。

应该按照$SPF_i$的值从小到大枚举，对于当前的物品，将最小值满足要求的人放入优先队列中进行维护，按照最大值来排序，从小到大。

然后判断优先队列中的元素的最大值是否大于当前物品的$SPF_i$，满足则答案加一。

其实用了这么多次的优先队列，我觉得基本上就是用来维护一个动态的数据。

完整代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

struct ty {
	int l, r, flag;
};
struct num {
	int n, c;
};
struct cmp {
	bool operator() (ty a, ty b) {
		return a.r > b.r;
	}
};

priority_queue<ty, vector<ty>,cmp> q;
vector<ty> t;
vector<num> n;

int cmp1(num a, num b) {
	return a.n < b.n;
}

int main() {
	int c, l; cin >> c >> l;
	for (int i = 0; i < c; i++) {
		int l, r; cin >> l >> r;
		t.push_back({ l,r,0 });
	}
	for (int i = 0; i < l; i++) {
		int s, c; cin >> s >> c;
		n.push_back({ s,c });
	}
	sort(n.begin(), n.end(), cmp1);
	int cnt = 0;
	for (int i = 0; i < l; i++) {
		for (int j = 0; j < c; j++) {
			if (!t[j].flag && t[j].l <= n[i].n) {
				t[j].flag = 1, q.push(t[j]);
			}
		}
		while (!q.empty() && n[i].c) {
			ty tmp = q.top(); q.pop();
			if (tmp.r >= n[i].n)	n[i].c--, cnt++;
		}
	}
	cout << cnt << endl;
}