【解题报告】 POJ3614 防晒

题目：防晒（已翻译）

解题思路：

模拟+贪心；

我们这道题是一道好的贪心的例题，我们只要对于每一头奶牛按照它们的minspf进行递减排序，然后在对于每一种防晒霜进行一次扫描，找出符合条件的spf值最大的防晒霜

但是会想到一点，我们需要将每一头奶牛的minspf和maxspf进行一一对应，所以我们可以使用结构体，然后自己在写一个比较函数，就可以让这两个数值一一对应，这样就方便多了

AC代码

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
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=2505;
int c,l,ans;
struct cow
{
	int minspf;
	int maxspf;
}a[maxn];
struct sc
{
	int spf;
	int cover;
}b[maxn];
int cmp(sc a,sc b)
{
    if(a.spf==b.spf)
    return a.cover>b.cover;
    return a.spf>b.spf;
}
int cmp2(cow a,cow b)
{
    if(a.minspf==b.minspf)
    return a.maxspf>b.maxspf;
    return a.minspf>b.minspf;
}
int main()
{
	cin>>c>>l;
	for(int i=1;i<=c;i++)
	cin>>a[i].minspf>>a[i].maxspf;
	sort(a+1,a+1+c,cmp2);
	for(int i=1;i<=l;i++)
	cin>>b[i].spf>>b[i].cover;
	sort(b+1,b+1+l,cmp);
	for(int i=1;i<=c;i++)
	{
		for(int j=1;j<=l;j++)
		{
			if(b[j].spf>=a[i].minspf&&b[j].spf<=a[i].maxspf&&b[j].cover)
			{
				ans++;
				b[j].cover--;
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}