BZOJ 1691 挑剔的美食家

发表于 | 分类于 | 评论数：

摘要

草有价格和味道，牛有对两者的下限要求，最小化价格的和。

好牛不恰烂饭！

[USACO 2007 DEC GOLD] Gourmet Grazers

题面

DarkBZOJ

HydroOJ

同题：洛谷 P2829

题解

贪心

牛按味道要求自高向低考虑，这样能吃的草的集合时不断变大的。

每头牛给予它能吃的最便宜的草即可：若最优解决策不同于此，可通过使代价不增的一系列调整变为此决策。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//https://darkbzoj.tk/problem/1691
//2021-10-10 sunshiness

#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

const int MAXN=100111;
const int MAXM=100111;

multiset<int> Set;

int N, M;

struct Pos{
	int x, y;
} Cow[MAXN], Grass[MAXM];

bool cmpy(const Pos &A, const Pos &B){
	return A.y>B.y;
}

int main(){
	
	scanf("%d%d", &N, &M);
	for(int i=1;i<=N;++i){
		scanf("%d%d", &Cow[i].x, &Cow[i].y);
	}
	for(int i=1;i<=M;++i){
		scanf("%d%d", &Grass[i].x, &Grass[i].y);
	}
	sort(Cow+1, Cow+N+1, cmpy);
	sort(Grass+1, Grass+M+1, cmpy);
	long long Ans=0LL;bool Flag=true;
	for(int i=1, j=1;i<=N;++i){
		while(j<=M && Grass[j].y>=Cow[i].y){
			Set.insert(Grass[j].x);++j;
		}
		multiset<int>::iterator it=Set.lower_bound(Cow[i].x);
		if(it==Set.end()){
			Flag=false;
			break;
		}
		Ans+=*it;Set.erase(it);
	}
	if(!Flag)	Ans=-1LL;
	printf("%lld\n", Ans);
	
	return 0;
}