poj 3614 Sunscreen 优先队列

缘起

日常浪费生命 poj 3614 Sunscreen

分析

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
有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤
了，太小奶牛没感觉。而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让
阳光照在身上的阳光强度固定为某个值。那么为了不让奶牛烫伤，又不会没有效果。给出了L种防晒霜。每种的数量和
固定的阳光强度也给出来了每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛最多有几个。

【输入】
第一行是C和L
1 ≤ C ≤ 2500
1 ≤ L ≤ 2500
然后是C行 每行两个整数 minSPFi、minSPFi
1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000
然后是L行，每行两个整数SPFi和coveri, 表示该种防晒霜固定的SPF值和能给多少头牛使用
1 ≤ SPFi ≤ 1,000

【输出】
最多能给几头奶牛使用

【样例输入】
3 2
3 10
2 5
1 5
6 2
4 1

【样例输出】
2

【限制】
1s

贪心策略还是想不到——QAQ，可耻的看了题解.

贪心策略如下

将牛按照_min升序排序, 然后将防晒霜按照spf升序排序. 例如牛排序为

1,2,3,4,5,6

防晒霜排序为

A,B,C,D

则对于A而言, 将_min<=A.spf的牛的_max值顺次入小根堆（这些可能领取A防晒霜）. 堆的好处在于可以快速求最小,求什么的最小? 求_max的最小. 然后顺次考虑出堆的牛. 对于_max>=A.spf的牛可以领取防晒霜.然后A.num–

对于_max<A.spf或者A.num已经变为0时，牛是无法领取A防晒霜的. 注意，堆是小根堆. 即算法优先让_max较小的牛领取防晒霜. 这是符合直观的. 因为_max大的还有机会在A防晒霜消耗完毕之后，领取B防晒霜. 而_max小的就根本没机会领取B防晒霜了（因为防晒霜是按照spf升序排序的，既然小于A.spf，就更小于B.spf了）

然后再用此算法运行B. 注意，B中的小根堆可能有上一轮A剩下的_max>=B.spf>=A.spf 但是因为A防晒霜耗尽而没有领取到防晒霜的牛.

基于上述贪心思想+堆优化，不难写出如下代码

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
//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef pair<int,int> P;

int C,L,ans;
P cows[2505];
P fss[2505];
priority_queue<int, vector<int>, greater<int> >pq; // 小根堆

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &C, &L);
	for (int i = 0;i<C;i++)
	{
		scanf("%d%d", &cows[i].first, &cows[i].second);
	}
	for (int i = 0;i<L;i++)
	{
		scanf("%d%d", &fss[i].first, &fss[i].second);
	}
	sort(cows,cows+C);
	sort(fss, fss+L);
	for (int i = 0,j=0; i<L; i++) // 逐步考察各个防晒霜
	{
		while(j<C&&cows[j].first<=fss[i].first) // 牛逐步进堆
		{
			pq.push(cows[j].second);
			j++;
		}
		while(!pq.empty() && fss[i].second) // 如果小根堆没有空并且防晒霜尚未耗尽, 所以可能pq没空，只是fss[i]耗尽了，pq中剩下的都是比较大的
		{
			int top = pq.top();
			pq.pop();
			if (top<fss[i].first)
			{
				continue;
			}
			ans++; // 此牛领取一瓶防晒霜
			fss[i].second--; // 少了一瓶防晒霜
		}
	}
	printf("%d\n",ans);
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 148kB
Length 994
Lang C++
Submitted 2019-08-29 17:10:56
Shared
RemoteRunId 20816034