POJ-3614 Sunscreen 题解

题目大意

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

解题思路

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

然后wa吐了。

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

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

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

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

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信