POJ 3614 Sunscreen（贪心优先队列）有助于理解贪心过程

本文主要是介绍POJ 3614 Sunscreen（贪心优先队列）有助于理解贪心过程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

Description
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they’re at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn’t tan at all…
The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.
What is the maximum number of cows that can protect themselves while tanning given the available lotions?
Input
Line 1: Two space-separated integers: C and LLines 2…C+1: Line i describes cow i’s lotion requires with two integers: minSPFi and maxSPFi
Lines C+2…C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri
Output
A single line with an integer that is the maximum number of cows that can be protected while tanning
Sample Input
3 2
3 10
2 5
1 5
6 2
4 1
Sample Output
2

题目大意：
有C头牛，每个牛都有对阳光的承受空间[minspf, maxspf]，有L种防晒霜，每种都对应有SPF值和瓶数，涂到牛身上可使其只受到SPF值的阳光，每瓶只可涂一头牛，问最多几只牛可以享受阳光。

解题思路：
此题可以视为在数轴上对区间进行操作：
在这里插入图片描述
上图中两头牛的防嗮区间分别为[1,4]和[2,3]
1、当防晒霜值为1时，只能给牛1用；
2、当防晒霜值为3时，牛1和牛2都有需求，那么我们应该给牛2，因为从图上看，牛2已经马上承受不住了，所以我们先给最大承受值较小的那头牛，再看看有没有适合牛1的；
3、当防晒霜值为4时，只能给牛1用。

下面来总结一下我们的贪心策略：
1、将牛的右边界从大到小排序；
2、将防晒霜按spf值从小到大排序；

对于排好序的牛，对于当前考虑的牛，假设有两瓶防晒霜 x < y可选，那么我们选x，因为x，y对于后面的牛来说有三种情况：

①x、y可选

②x不可选，y可选

③x、y均不可选

那么我们选择小的(即x)就对后面的牛来说影响最小

AC代码(贪心)：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct cow {int minnum, maxnum;
}list1[2501];
struct fangshaishuang {int v, num;
}list2[2501];
bool cmp1(cow a, cow b) { return a.maxnum < b.maxnum; }
bool cmp2(fangshaishuang a, fangshaishuang b) {return a.v < b.v;
}int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d%d", &list1[i].minnum, &list1[i].maxnum);}for (int i = 1; i <= m; i++) {scanf("%d%d", &list2[i].v, &list2[i].num);}sort(list1 + 1, list1 + 1 + n, cmp1);sort(list2 + 1, list2 + 1 + m, cmp2);int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (list2[j].v >= list1[i].minnum&&list2[j].v <= list1[i].maxnum&&list2[j].num > 0) {ans++; list2[j].num--;break;}}}cout << ans << endl;
}

解题过程中也参考了很多大神们的博客，发现有好多大神都选择了优先队列的写法：

将奶牛按照防晒范围的最小值升序排序，将防晒霜的值也进行升序排序，从最小的防晒霜值开始考虑，将最小值小于等于该防晒霜值的奶牛拿出来，把它们区间的右边界放入优先队列之中(优先队列中最小值先出)，就可将这些右边界中最小的取出来，更新答案。

优先队列写法：
AC代码

#include<iostream>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;struct cow {int l, r;
}list1[2501];
struct suns {int v, num;
}list2[2501];
bool cmp1(cow a, cow b) { return a.l < b.l; }
bool cmp2(suns a, suns b) { return a.v < b.v; }
priority_queue<int, vector<int>, greater<int> > que;
int main() {int c, l;cin >> c >> l;for (int i = 1; i <= c; i++) { cin >> list1[i].l >> list1[i].r; }for (int i = 1; i <= l; i++) { cin >> list2[i].v >> list2[i].num; }sort(list1 + 1, list1 + 1 + c, cmp1);sort(list2 + 1, list2 + 1 + l, cmp2);int j = 1;//从第一头牛开始考虑int ans = 0;for (int i = 1; i <= l; i++) {//对每一种防晒霜进行考虑while (j <= c&&list1[j].l <= list2[i].v) {//将所有左边界小于防晒霜值的牛的右边界都压进优先队列que.push(list1[j].r);j++;}while (list2[i].num > 0 && !que.empty()) {int tmp = que.top();que.pop();if (tmp >= list2[i].v) {//如果当前右边界最小的牛可以用list2[i].num--;ans++;}}}cout << ans << endl;
}