题目链接：http://poj.org/problem?id=3614
题意：C头牛去晒太阳，每头牛有自己所限定的spf安全范围[min, max]；有L瓶防晒液，每瓶有自己的spf值和容量（能供几头牛用）。
求这L瓶防晒液最多能让多少头牛安全地晒太阳。
思路：贪心策略，按spf从小到大或从大到小的顺序取出防晒液，供给尽可能多的剩余的牛。
具体如何判断当前这瓶防晒液最多能供给几头牛呢？
以spf从小到大排序所有防晒液为例，可以维护一个小顶堆，每取出一瓶防晒液l，就把剩余的所有min值低于l.spf的牛的max值放入堆中。
接下来在l的容量尚未耗尽时，反复弹出并比较堆顶值与l.spf，若大于l.spf，则 l 消耗1单位的容量供给这头牛，计数值加1；否则这头牛不能被任何防晒液供给（当前spf已经是剩余的最小值，后续不会有更小的）。反复取堆顶元素直至容量耗尽或堆变空。各瓶防晒液的计数值的总和即为答案。
首先需要将防晒液按spf值从小大到排序（O(LlogL)），以及将牛按min值从小到大排序(O(ClogC))；然后外层循环对L瓶防晒液进行一遍扫描(O(L))，内层循环每头牛的max必然入堆一次、弹出一次(Ω(C))，所以总的复杂度为O(LlogL + CLogC + LC)。
自己实现的堆，时间上总是比STL的priority_queue慢一些，不过空间更少。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_C = ;
const int MAX_L = ;
int C, L;
struct Cow
{
int min, max;
Cow& operator = (Cow& c){
min = c.min;
max = c.max;
return *this;
}
}cows[MAX_C]; struct Lotion
{
int spf,cover;
}lotions[MAX_C]; bool cmpL(Lotion l1, Lotion l2){
return l1.spf < l2.spf;
}
bool cmpC(Cow c1, Cow c2){
return c1.min < c2.min;
} int heap[MAX_C]; //小顶堆
int size = ; void swap(int& x, int& y){
int tmp = x;
x = y;
y = tmp;
} void insert(int x){
size++;
heap[size-] = x;//目标元素暂时插到末尾
int i = size - ;//候选目标位置
while(i > ){ //上滤，反复与父节点比较
int p = (i-)/;
if(heap[p] > heap[i]){//与父节点违反堆序性时
swap(heap[i], heap[p]);//父节点下沉
i = p; //候选位置攀升
}else break;
}
} void deleteTop(){
heap[] = heap[size-];
size--;
int i = ; //候选目标位置
while(i*+ < size){//下滤
int lc = i*+;
int rc = i*+;
int c = lc;
if(rc<size && heap[rc]<heap[lc])
c = rc;
if(heap[c] < heap[i]){
swap(heap[c], heap[i]);//孩子节点攀升
i = c;//候选位置下沉
}else break;
}
} int getTop(){
return heap[];
} int main()
{
freopen("3614.txt", "r", stdin);
scanf("%d%d", &C, &L);
for(int i=; i<C; i++){
scanf("%d%d", &cows[i].min, &cows[i].max);
} for(int i=; i<L; i++){
scanf("%d%d", &lotions[i].spf, &lotions[i].cover);
} sort(lotions, lotions+L, cmpL);
sort(cows, cows+C, cmpC); int cnt = ;
for(int i=, j=; i<L; i++){
//printf("lotion %d %d\n", lotions[i].spf, lotions[i].cover);
while(j<C && cows[j].min <= lotions[i].spf){
insert(cows[j].max);
j++;
//printf("insert %d\n", cows[j-1].max);
}
int vol = lotions[i].cover; while(vol > && size>){
if(getTop() >= lotions[i].spf){
vol--;
cnt++;
//printf("add %d\n", getTop());
}
deleteTop();
//printf("%d\n", cnt);
}
}
printf("%d\n", cnt);
return ;
}