[文章目录]
Description
与很多奶牛一样，Farmer John那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。
现在，Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1 <= N <= 100,000)头挑剔的奶牛。
所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1 <= A_i <= 1,000,000,000)，并且鲜嫩程度不能低于B_i(1 <= B_i <= 1,000,000,000)。
商店里供应M(1 <= M <= 100,000)种不同的牧草，第i种牧草的定价为C_i(1 <= C_i <= 1,000,000,000)，鲜嫩程度为D_i (1 <= D_i <= 1,000,000,000)。
为了显示她们的与众不同，每头奶牛都要求她的食物是独一无二的，也就是 说，没有哪两头奶牛会选择同一种食物。
Farmer John想知道，为了让所有奶牛满意，他最少得在购买食物上花多少 钱。
不会写treap的我写了一个set。题目分析就是对于每一个牛，要找一个能满足条件的草，使得价格尽量小。贪心思想就是先按鲜嫩程度排序，再将满足足够鲜嫩条件的草里找一个价格最小的。并且由于没有相同的草，所以要进行删除。（排序+删除==treap<multiset>）
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <algorithm>
#define LL long long
using namespace std;
int n,m;
LL ans;
struct node
{
LL w,v;
}a[110000],b[110000];//a->cow
bool cmp(node x,node y)
{
return x.w>y.w;
}
bool operator < (node x,node y)
{
return x.v<y.v;
}
multiset<node>s;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i].v,&a[i].w);
for(int i=1;i<=m;i++)
scanf("%lld%lld",&b[i].v,&b[i].w);
sort(a+1,a+n+1,cmp);
sort(b+1,b+m+1,cmp);
int cnt=1;
multiset<node>::iterator it;
for(int i=1;i<=n;i++)
{
while(b[cnt].w>=a[i].w&&cnt<=m)
s.insert(b[cnt]),cnt++;
it=s.lower_bound(a[i]);
if(it!=s.end())
s.erase(it),ans+=it->v;//高级清真写法
else
{
printf("-1");
return 0;
}
}
printf("%lld",ans);
return 0;
}迭代器，set，自定义符号一起抓2333