【贪心训练】挑剔的美食家

题目描述

与很多奶牛一样，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想知道，为了让所有奶牛满意，他最少得在购买食物上花多少钱。

思路：

我们先介绍一个STL：multiset
这个东西很厉害，可以logn的复杂度查找，插入，删除元素。
它里面的元素是可以重复的。
重要的是，它是一个有序数列，还可以在上面进行lower_bound操作。
介绍完毕。

我们先按品质从大到小排序，然后直接把品质大于当前奶牛的放进multiset里。
然后每次用二分查找大于最小钱数的最小线数就行了。

$code$

#include

using namespace std;

const int MAXN = 1e5 + 10;

int n, m;
long long ans;
struct node {
	int x, y;
}a[MAXN], b[MAXN];

multiset<int> q;

bool cmp(node x, node y) {
	return x.y > y.y;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%d%d", &a[i].x, &a[i].y);
	for(int i = 1; i <= m; i ++) scanf("%d%d", &b[i].x, &b[i].y);
	sort(a + 1, a + 1 + n, cmp);
	sort(b + 1, b + 1 + m, cmp);
	int j = 1;
	for(int i = 1; i <= n; i ++) {
		while(b[j].y >= a[i].y && j <= m) q.insert(b[j].x), j ++;
		multiset<int>::iterator tmp = q.lower_bound(a[i].x);
		if(tmp == q.end()) {
			printf("-1");
			return 0;
		}
		ans += *tmp;
		q.erase(tmp); 
	}
	printf("%lld", ans);
	return 0;
}