Algoogle

Algorithm for Programming Contest

PKU 3622 Gourmet Grazers

Category: PKU Tag: greedy

Gourmet Grazers

問題概要


N匹の牛がいて, それぞれ価値Ai以上, 新鮮さBi以上の草しか食べない.
M個の草が売られていて, それぞれ価値Ci, 新鮮さDiとなっている
すべての牛に条件を満たす草を与えるときの価値の総和の最小を求めよ.

解法


草の条件が大きい牛から順にみていき, それぞれそれ以上になる草の価値を全てmultisetに突っ込む.
multisetに入っている価値のうち牛の条件をみたす最小の価値の草がその牛に与える草.
その価値より大きい草を与える意味は皆無.

コード


(3622.cpp) download
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
#include <algorithm>
#include <cstdio>
#include <queue>
#include <set>
#include <map>

using namespace std;
#define int long long
typedef pair<int,int> pii;
int N, M;
pii dem[100010], shp[100010];
multiset<int> C;

int solve(){
    int ret = 0, j = M-1;
    for(int i = N-1; i >= 0; i--){
        while(j >= 0 and dem[i].first <= shp[j].first)
            C.insert(shp[j--].second);
        multiset<int>::iterator itr = C.lower_bound(dem[i].second);
        if(itr == C.end()) return -1LL;
        ret += *itr;
        C.erase(itr);
    }
    return ret;
}

signed main(){
    scanf("%lld%lld", &N, &M);
    for(int i = 0; i < N; i++){
        int a, b;
        scanf("%lld%lld", &a, &b);
        dem[i] = pii(b, a);
    }
    sort(dem, dem+N);
    for(int i = 0; i < M; i++){
        int c, d;
        scanf("%lld%lld", &c, &d);
        shp[i] = pii(d, c);
    }
    sort(shp, shp+M);
    printf("%lld\n", solve());
    return 0;
}

Comments