POJ 3614 Sunscreen

Sunscreen

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2616		Accepted: 925

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 ≤ minSPF_i ≤ 1,000; minSPF_i≤ maxSPF_i ≤ 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 SPF_i (1 ≤ SPF_i ≤ 1,000). Lotion bottle i can cover cover_i 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 L * Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPF_i and maxSPF_i * Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPF_i and cover_i

Output

A single line with an integer that is the maximum number of cows that can be protected while tanning

Sample Input

Sample Output

一道有点难的贪心加优先队列问题

具体思路在代码的注释中有详细说明

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 typedef struct
 8 {
 9     int minspf;
10     int maxspf;
11 } COW;
12 
13 typedef struct
14 {
15     int spf;
16     int cover;
17 } LOTION;
18 
19 int c,l,sz=0;
20 COW cow[2550],heap[2550];
21 LOTION lotion[2550];
22 
23 bool cmp_cow(COW a,COW b)
24 {
25     return a.minspf<b.minspf;
26 }
27 
28 bool cmp_lotion(LOTION a,LOTION b)
29 {
30     return a.spf<b.spf;
31 }
32 
33 //对牛维护一个小根堆，键值为所需防晒霜最大能力
34 void push(COW x)
35 {
36     int i=sz++;
37     while(i>0)
38     {
39         int p=(i-1)/2;
40         if(heap[p].maxspf<=x.maxspf)
41             break;
42         heap[i]=heap[p];
43         i=p;
44     }
45     heap[i]=x;
46 }
47 
48 COW pop()
49 {
50     COW ret=heap[0];
51     COW x=heap[--sz];
52     int i=0;
53     while(i*2+1<=sz)
54     {
55         int a=i*2+1,b=i*2+2;
56         if(b<sz&&heap[b].maxspf<heap[a].maxspf)
57             a=b;
58         if(heap[a].maxspf>=x.maxspf)
59             break;
60         heap[i]=heap[a];
61         i=a;
62     }
63     heap[i]=x;
64     return ret;
65 }
66 
67 int main()
68 {
69     while(scanf("%d %d",&c,&l)==2)
70     {
71         sz=0;
72         for(int i=0;i<c;i++)
73             scanf("%d %d",&cow[i].minspf,&cow[i].maxspf);
74         for(int i=0;i<l;i++)
75             scanf("%d %d",&lotion[i].spf,&lotion[i].cover);
76         sort(cow,cow+c,cmp_cow);//将所有牛按它们所需防晒霜的最小防晒能力排序
77         sort(lotion,lotion+l,cmp_lotion);//将将所有防晒霜按它们的防晒能力排序
78         int ans=0,t=0;
79         for(int i=0;i<l;i++)
80         {
81             while(t<c&&lotion[i].spf>=cow[t].minspf)//对于每一种防晒霜，先将所有最小值比它大的牛插入堆中
82             {
83                 push(cow[t]);
84                 t++;
85             }
86             while(sz>0&&lotion[i].spf>heap[0].maxspf)//再将所有最大值比它小的牛出堆
87                 pop();
88             while(lotion[i].cover>0&&sz>0)//最后将所有它能保护的牛出堆并将答案+1
89             {
90                 pop();
91                 ans++;
92                 lotion[i].cover--;
93             }
94         }
95         printf("%d
",ans);
96     }
97 
98     return 0;
99 }

[C++]