poj 3614

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[ 2555 ];

struct suns{
    int num,val;
}bot[ 2555 ];
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 = 0,tmp = 1;
    priority_queue<int, vector<int>, greater<int> >s;       //构建一个大值优先的优先队列
    scanf("%d%d",&c,&l);
    for(int i = 1 ; i <= c ; i++)
        scanf("%d%d",&cow[i].mi,&cow[i].ma);
    for(int i = 1 ; i <= l ; i++)
        scanf("%d%d",&bot[i].val,&bot[i].num);
    qsort(cow,c + 1,sizeof(cow[0]),cmp);                     //对奶牛和防晒霜进行排序。
    qsort(bot,l + 1,sizeof(bot[0]),cmp1);
    for(int i = 1 ; 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
",ans);
    return 0;
}