POJ 3614 Sunscreen（贪心，区间单点匹配）

把牛的SPF看作一个区间，防晒霜看作点。一个点可以匹配C[i]次，问最大匹配数。可以用图论做。

也可以贪心。贪心的思想是，把区间和点排序以后，考虑最左边的点，加入和这个点相交的区间，

并排除出界的区间，优先选右端点最小的区间进行匹配。

对于已有的区间，左端点已经可以忽略，因为已经没有更靠左的点可以选。

而且右端点越大的选到的机会越大，所以放在后面选。

（如果一个区间要匹配多次的话贪心可能会出错

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;

const int maxn = 2505;
struct BinaryHEAP
{
    int Heap[maxn];
    int sz;
    #define Cmp(a,b) ((a)<(b)) //small
    void push(int x)
    {
        int i = ++sz;
        while(i > 1){
            int p = i>>1;
            if(!Cmp(x,Heap[p])) break;
            Heap[i] = Heap[p];
            i = p;
        }
        Heap[i] = x;
    }

    void pop()
    {
        int x = Heap[sz--];
        int i = 1;
        while((i<<1)<=sz){
            int a = i<<1, b = i<<1|1;
            if(b<=sz && Cmp(Heap[b],Heap[a])) a = b;
            if(!Cmp(Heap[a],x)) break;
            Heap[i] = Heap[a];
            i = a;
        }
        Heap[i] = x;
    }

    int operator[](int x){ return Heap[x]; }
}q;


#define MP make_pair
#define fi first
#define se second

pair<int,int> cow[maxn], lot[maxn];

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int C,L; cin>>C>>L;
    for(int i = 0; i < C; i++){
        scanf("%d%d",&cow[i].fi,&cow[i].se);
    }
    for(int i = 0; i < L; i++){
        scanf("%d%d",&lot[i].fi,&lot[i].se);
    }
    sort(lot,lot+L);
    sort(cow,cow+C);
    int ans = 0;
    for(int i = 0, j = 0; i < L; i++){
        while(j < C && cow[j].fi <= lot[i].fi) {
            q.push(cow[j++].se);
        }
        while(q.sz && q[1] < lot[i].fi ) q.pop();
        while(q.sz && lot[i].se--){
            ans++; q.pop();
        }
    }
    printf("%d
",ans);
    return 0;
}