https://vjudge.net/problem/POJ-3614
如果这不是优先队列专题里的，我可能不一定能想到这么做。
结构体命名得有点不好，解题中看着Edge这个不恰当的命名，思路老是断掉。
贪心策略：先对牛按from升序，对瓶子按w升序，优先队列是按to的小顶堆；
然后枚举瓶子，只要当前牛的from<=当前瓶子的w就入队，直到不满足为止；
然后在队伍里取出一个，判断它的是否to>=w以及cover数是否还够用。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
using namespace std;
int n, m;
struct Node{
int from, to;
int w;
friend bool operator<(const Node a, const Node b){
return a.to>b.to;//小顶堆按to排
}
}node[];
struct Edge{
int w, cover;
}edge[];
bool cmp(const Edge a, const Edge b)
{
return a.w<b.w;
}
bool cmp2(const Node a, const Node b)
{
return a.from<b.from;
}
int main()
{
priority_queue<Node> q;
cin >> n >> m;
for(int i = ; i < n; i++){
cin >> node[i].from >> node[i].to;
}
for(int i = ; i < m; i++){
cin >> edge[i].w >> edge[i].cover;
}
sort(edge, edge+m, cmp);
sort(node, node+n, cmp2);//一开始没加这个wa了好久
int k = , ans=;
for(int i = ; i < m; i++){//瓶子
while(k < n&&node[k].from<=edge[i].w){//左边界在它的前面就入队
q.push(node[k]);
k++;
}
while(!q.empty()){
Node t = q.top(), p;
q.pop();
if(t.to>=edge[i].w&&edge[i].cover>){//两种都满足可以ans++
edge[i].cover--;
ans++;
}
if(edge[i].cover == ) break; }
}
cout << ans << endl;
return ;
}