51nod 挑剔的美食家

基准时间限制：1 秒空间限制：131072 KB 分值: 5

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

Input

* 第1行: 2个用空格隔开的整数：N 和 M

* 第2..N+1行: 第i+1行包含2个用空格隔开的整数：A_i、B_i * 第N+2..N+M+1行: 第j+N+1行包含2个用空格隔开的整数：C_i、D_i

Output

* 第1行: 输出1个整数，表示使所有奶牛满意的最小花费。如果无论如何都无法 满足所有奶牛的需求，输出-1

Input示例

Output示例

12

还是STL大法好啊，一开始想了各种稀奇古怪的解法来做。。。。
思路:先将牛跟草按鲜嫩程度降序排序，然后枚举每一头牛，将鲜嫩程度大于等于该牛的存起来，然后找第一个大于等于该牛的价格的草；
并将用过的草删除掉不能再用（由于我们是按照鲜嫩程度降序排序，所以若是满足第i头牛，则一定可以满足第i+1头牛）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn = 100010;
 7 struct Task{
 8     LL L, R;
 9     bool operator<(const Task&a)const {
10         if (R == a.R)return L > a.L;
11         return R > a.R;
12     }
13 };
14 Task a[maxn], b[maxn];
15 LL n, m, ans = 0;
16 bool solve()
17 {
18     multiset<LL> S;
19     multiset<LL>::iterator it;
20     int tmp = 1;
21     for (int i = 1; i <= n; i++) {
22         while (b[tmp].R >= a[i].R)S.insert(b[tmp++].L);
23         it = S.lower_bound(a[i].L);
24         if (it == S.end())return false;
25         ans += *it;
26         S.erase(it);
27     }
28     return true;
29 }
30 int main()
31 {
32     ios::sync_with_stdio(false);
33     while (cin >> n >> m) {
　　　　　　 ans = 0;
34         for (int i = 1; i <= n; i++)
35             cin >> a[i].L >> a[i].R;
36         for (int i = 1; i <= m; i++)
37             cin >> b[i].L >> b[i].R;
38         sort(a + 1, a + n + 1);
39         sort(b + 1, b + m + 1);
40         if(solve())    cout << ans << endl;
41         else cout << "-1" << endl;
42     }
43     return 0;
44 }

51nod 挑剔的美食家

推荐阅读