POJ 3614 Sunscreen

http://poj.org/problem?id=3614

贪心的思路：

因为每只cow有minSPF maxSPF这么一个区间那么

先确定minSPF 这么一个值（从小到大排列）-->>数组排

将lotion 的spf也从小到大排列这样相当于确定有多少 cow 可以在minSPF这个点满足使用的条件

然后再在maxSPF（ --->>> 用堆按maxSPF降序存）这一条件贪心

每次让满足minSPF 条件的cow先使用lotion 这样越苛刻的先满足那么使策略最优

然后最开始想到的用区间大小来贪心(先让区间小的用) 是有问题的

反例

1 9

2 5

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 #include <algorithm>
 6 #define MAXN 2507
 7 using namespace std;
 8 typedef pair<int,int> P;
 9 struct Cow
10 {
11     int minSPF, maxSPF;
12     int num;//后面标记要用的编号
13     bool cover;
14     bool operator < (Cow c) const
15     {
16         return maxSPF > c.maxSPF;
17     }
18 };
19 
20 bool cmp(Cow a, Cow b)
21 {
22     return a.minSPF < b.minSPF;
23 }
24 
25 priority_queue<Cow> que;
26 Cow cow[MAXN];
27 P lotion[MAXN];
28 //Cow cow[MAXN];
29 int ans = 0;
30 int main()
31 {
32     int C, L;
33     freopen("in.txt", "r", stdin);
34     scanf("%d%d", &C, &L);
35     for (int i = 0; i < C; i++)
36     {
37         int maxspf, minspf;
38         scanf("%d%d", &minspf, &maxspf);
39         cow[i].minSPF = minspf;
40         cow[i].maxSPF = maxspf;
41         cow[i].cover = false;
42     }
43     for (int i = 0; i < L; i++)
44     {
45         int spf, cover;
46         scanf("%d%d", &spf, &cover);
47         lotion[i] = P(spf, cover);
48     }
49     sort(cow, cow+C, cmp);
50     sort(lotion, lotion+L);
51     //for (int i = 0; i < C; i++) cout << cow[i].minSPF << " " << cow[i].maxSPF  << endl;
52     for (int i = 0; i < L; i++)
53     {
54         for (int j = 0; j < C; j++)
55         {
56             cow[j].num = j;
57             if (cow[j].minSPF <= lotion[i].first && !cow[j].cover)
58             {
59                 que.push(cow[j]);
60             }
61             else if (!cow[j].cover) break;
62         }
63         while (!que.empty() && lotion[i].second)
64         {
65             Cow tmp = que.top();
66             que.pop();
67             if (tmp.maxSPF >= lotion[i].first)
68             {
69                 cow[tmp.num].cover = true;//本来想用指针直接 改true 但是 用来指针 有限队列无法排序了 变成普通的队列了
70                 lotion[i].second--;
71                 ans++;
72             }
73         }
74         while(!que.empty()) que.pop();
75     }
76     printf("%d
", ans);
77     return 0;
78 }