POJ 3622 - Gourmet Grazers

http://poj.org/problem?id=3622

概要

N 頭の牛が「値段が A[i] 以上で greeness が B[i] 以上の草が欲しい」と言っている． M 個店があり，値段が C[i] で greenness が D[i] な草を売っている． 複数の牛が同じ店で草を買うことはできない．

すべての牛の要求を満たすのに必要な最低のコストを答える． ただし，要求を満たせない場合は -1 を答える．

制約

解法

要求と店をそれぞれ B, D でソートして大きいほうから見ていき， B[i] <= D[j] な店の中から，A[i] 以上で最も安い店を順に選んでいけばよい．

「B[i] <= D[j] な店の値段」は multiset で管理し，「A[i] 以上で最も安い店」を対数オーダーで探せるようにした．

 1 #include <cstdio>
 2 #include <set>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N, M;
 9   scanf("%d %d", &N, &M);
10   typedef pair<long long, long long> pll;
11   static pll ba[100000];
12   for (int i = 0; i < N; i++) {
13     scanf("%lld %lld", &ba[i].second, &ba[i].first);
14   }
15   static pll dc[100000];
16   for (int i = 0; i < M; i++) {
17     scanf("%lld %lld", &dc[i].second, &dc[i].first);
18   }
19 
20   sort(ba, ba+N, greater<pll>());
21   sort(dc, dc+M, greater<pll>());
22   int j = 0;
23   multiset<long long> s;
24   long long ans = 0LL;
25   for (int i = 0; i < N; i++) {
26     for (; j < M && dc[j].first >= ba[i].first; j++) {
27       s.insert(dc[j].second);
28     }
29     multiset<long long>::const_iterator it = s.lower_bound(ba[i].second);
30     if (it == s.end()) {
31       ans = -1LL;
32       break;
33     } else {
34       ans += *it;
35       s.erase(it);
36     }
37   }
38   printf("%lld\n", ans);
39   return 0;
40 }
poj/3622.cc