题目描述

约翰的奶牛对食物越来越挑剔了。现在,商店有M 份牧草可供出售,奶

牛食量很大,每份牧草仅能供一头奶牛食用。第i 份牧草的价格为Pi,口感为

Qi。约翰一共有N 头奶牛,他要为每头奶牛订购一份牧草,第i 头奶牛要求

它的牧草价格不低于Ai,口感不低于Bi。请问,约翰应该如何为每头奶牛选

择牧草,才能让他花的钱最少?

输入输出格式

输入格式:
  • Line 1: Two space-separated integers: N and M.
  • Lines 2..N+1: Line i+1 contains two space-separated integers: Ai and Bi
  • Lines N+2..N+M+1: Line i+N+1 contains two space-separated integers: Ci and Di
输出格式:
  • Line 1: A single integer which is the minimum cost to satisfy all the cows. If that is not possible, output -1.
输入输出样例
输入样例#1:

4 7
1 1
2 3
1 4
4 2
3 2
2 1
4 3
5 2
5 4
2 6
4 4

输出样例#1:

12


这题是个贪心,考虑一下按口感度降序排列可供的牧草和奶牛,
假如现在是第 i 头奶牛,
从降序排列的牧草中选择满足他口感的牧草,
加入某个数据结构中(雾)
然后贪心地找不低于他要求的价格的牧草中最小的
删除吃掉
可以发现对于下一头奶牛 j
现有数据结构中的牧草必定满足他的口感(因为是降序排序的)
这样就要求这个数据结构可以
1.加入某个数
2.删除某个数
3.求某个数的后继
所以我们可以直接上平衡树(STL也可以)
这里写的是FHQTreap

 


常数惨不忍睹…

分类: 数据结构题解

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
_mxg Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
_mxg
游客

太聚~(≧▽≦)/~啦啦啦