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 L * Lines 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

Sample Output

Source

USACO 2007 November Gold

题意：

有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤了，太小奶牛没感觉。

而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。

那么为了不让奶牛烫伤，又不会没有效果。

给出了L种防晒霜。每种的固定的阳光强度和数量也给出来了

每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛有几个。

思路：刚开始想错了，正确的方法为：

1、将牛按最小值从小到大排好序

2、将防嗮霜按阳光强度从小到大排好序

3、然后有一个优先队列，优先队列里按牛的最大值从小到大排序

4、遍历防晒霜，将牛的最小值<=防晒霜的值的牛push进优先队列，然后根据防晒霜的数量从队首开始选出符合的牛，这部分见代码

5、while(k<n && cow[k].l<=p[i].x)注意这里的判断条件要写在一起，刚开始分开写，将第二个条件写在下面的if中，结果TLE了。。。。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<algorithm>
 6 #include<vector>
 7 using namespace std;
 8 #define N 2600
 9 int n,m;
10 struct Node{
11     int l,r;
12     bool friend operator < (Node a,Node b){
13         return a.r>b.r;
14     } 
15 }cow[N];
16 struct Node1{
17     int x,num;
18 }p[N];
19 bool cmp(Node a,Node b){
20     return a.l<b.l;    
21 }
22 bool cmp1(Node1 a,Node1 b){
23     return a.x<b.x;
24 }
25 int main()
26 {
27     while(scanf("%d%d",&n,&m)==2){
28         
29         for(int i=0;i<n;i++){
30             scanf("%d%d",&cow[i].l,&cow[i].r);
31         }
32         for(int i=0;i<m;i++){
33             scanf("%d%d",&p[i].x,&p[i].num);
34         }
35         sort(cow,cow+n,cmp);
36         sort(p,p+m,cmp1);
37         
38         //for(int i=0;i<v.size();i++){
39         //    printf("---%d
",v[i]);
40         //}
41         
42         priority_queue<Node>q;
43         
44         int k=0;
45         int ans=0;
46         for(int i=0;i<m;i++){
47             while(k<n && cow[k].l<=p[i].x){
48                     q.push(cow[k]);
49                     k++;
50             }
51             
52             int w=0;
53             while(!q.empty()){
54                 
55                 if(w>=p[i].num) break;
56                 
57                 Node tmp=q.top();
58                 if(tmp.r>=p[i].x){
59                     q.pop();
60                     ans++;
61                     w++;
62                 }
63                 else{
64                     q.pop();
65                 }
66                 
67             }
68         }
69         printf("%d
",ans);
70     }
71     return 0;
72 }

View Code