poj3614

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

题意：有n头奶牛想要晒太阳，但他们每个人对太阳都有不同的耐受程度，也就是说，太阳不能太大也不能太小，现在有一种防晒霜，涂抹这个防晒霜可以把太阳的强度固定到一个值

求一共有多少头奶牛可以晒太阳

 #include <stdio.h>

 #include <queue>

 #include <stdlib.h>

 using namespace std;

 int m,n;

 struct co{

     int mi,ma;

 }cow[  ];

 struct suns{

     int num,val;

 }bot[  ];

 int cmp(const void *a,const void *b)

 {

     return (*(co *)a).mi-(*(co *)b).mi;

 }

 int cmp1(const void *a,const void *b)

 {

     return (*(suns *)a).val-(*(suns *)b).val;

 }

 int main()

 {

     int c,l,ans = ,tmp = ;

     priority_queue<int, vector<int>, greater<int> >s;       //构建一个大值优先的优先队列

     scanf("%d%d",&c,&l);

     for(int i =  ; i <= c ; i++)

         scanf("%d%d",&cow[i].mi,&cow[i].ma);

     for(int i =  ; i <= l ; i++)

         scanf("%d%d",&bot[i].val,&bot[i].num);

     qsort(cow,c + ,sizeof(cow[]),cmp);                     //对奶牛和防晒霜进行排序。

     qsort(bot,l + ,sizeof(bot[]),cmp1);

     for(int i =  ; i <= l ; i++)

     {

         while(tmp <= c && cow[tmp].mi <= bot[i].val)      //把可以用这种防晒霜奶牛进队列

         {

             s.push(cow[tmp++].ma);

         }

         while(!s.empty()&&bot[i].num)                       //然后计算这一种防晒霜可以在几头牛上用

         {

             int x = s.top();

             s.pop();

             if(x<bot[i].val) continue;

             ans++;

             bot[i].num--;

         }

     }

     printf("%d\n",ans);

     return ;

 }