Gourmet Grazers
题目大意
约翰的奶牛对食物越来越挑剔了。现在，商店有(M) 份牧草可供出售，奶牛食量很大，每份牧草仅能供一头奶牛食用。第(i) 份牧草的价格为(P_i)，口感为(Q_i)。约翰一共有N 头奶牛，他要为每头奶牛订购一份牧草，第(i)头奶牛要求它的牧草价格不低于(A_i)，口感不低于(B_i)。请问，约翰应该如何为每头奶牛选择牧草，才能让他花的钱最少？
贪心。
贪心策略就是根据草的鲜嫩程度从大到小排序，选择草的鲜嫩程度和定价>=奶牛的需求并且定价最小的草。然后把草的定价累加，将选定的草删除。因为要查找在容器里与奶牛需求接近的草的定价，所以要用multiset维护，将草的鲜嫩程度>=奶牛甩进去，再二分查找定价最小的草，能够过全部数据。
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
int n,m;
long long ans;
struct edge{
int dil,pri;
}cow[200000],com[200000];
bool cmp(edge x,edge y){
if(x.dil==y.dil)return x.pri>y.pri;
else return x.dil>y.dil;
}
struct cmb
{
bool operator()(int a, int b)
{
return a<b;
}
};
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&cow[i].pri,&cow[i].dil);
for(int i=1;i<=m;i++){
scanf("%d%d",&com[i].pri,&com[i].dil);
}
sort(cow+1,cow+1+n,cmp);
sort(com+1,com+1+m,cmp);
multiset<int, cmb>s;
multiset<int, cmb>::iterator it;
int j=1,flag=1;
for(int i=1;i<=n;i++){
while(com[j].dil>=cow[i].dil && j<=m) s.insert(com[j++].pri);
it = s.lower_bound(cow[i].pri);
if(it==s.end()){
flag=0;
break;
}
ans += *it;
s.erase(it);
}
if(!flag)puts("-1");
else
cout << ans;
return 0;
}