Algoogle

Algorithm for Programming Contest

PKU 3614 Sunscreen

Category: PKU Tag: greedy

Sunscreen

問題概要


日焼け止めを牛に塗りたい. 各牛には有効なspfの範囲があり, 各日焼け止めはspfと使える数が決まっている.

解法


spfが小さいものから日焼け止めを選び, それが使える牛をリストアップする.
そのなかでspfの上限が小さい牛から順に選べば良い.

コード


(3614.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
44
45
#include <algorithm>
#include <cstdio>
#include <map>

using namespace std;

typedef pair<int,int> pii;

int C, L;
int used[2510];
pii cows[2510], loti[2510];

int main(){
    scanf("%d%d", &C, &L);

    for(int i = 0; i < C; i++){
        int l, u; scanf("%d%d", &l, &u);
        cows[i] = pii(l,u);
    }
    sort(cows, cows+C);

    for(int i = 0; i < L; i++){
        int s, n; scanf("%d%d", &s, &n);
        loti[i] = pii(s, n);
    }
    sort(loti, loti+L);

    int ans = 0;
    for(int i = 0; i < L; i++){
        int spf = loti[i].first, res = loti[i].second, cnt = 0;
        pii cand[2510];
        for(int j = 0; j < C; j++){
            if(used[j]) continue;
            if(cows[j].first > spf) break;
            if(cows[j].first <= spf and spf <= cows[j].second) cand[cnt++] = pii(cows[j].second, j);
        }
        sort(cand, cand+cnt);
        ans += min(cnt, res);
        for(int j = 0; j < min(cnt, res); j++)
            used[cand[j].second] = 1;
    }

    printf("%d\n", ans);
    return 0;
}

Comments