Algoogle

Algorithm for Programming Contest

PKU 2010 Moo University - Financial Aid

Category: PKU Tag: data-structure, greedy

Moo University - Financial Aid

問題概要


C個の中からコストの和がF以下になるようにN個選ぶとき, そのN個の価値の中央値の最大を求めよ

解法


まず価値でソートする.
中央値を決めると, そのときの他のN-1個の最善の選び方は
それより価値が大きいものからコストが小さい順にN/2個
それより価値が小さいものからコストが小さい順にN/2個
になる.
前からx個の中でN/2個選ぶときのコストの総和の最小値と
後からx個の中でN/2個選ぶときのコストの総和の最小値を予め求めておけばよい.
priority_queueなどを使えばできる.
あとは価値が大きい方から中央値を決めて条件を満たせるか試せばいい.

コード


(2010.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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <algorithm>
#include <cstdio>
#include <queue>
#include <map>

using namespace std;

typedef pair<int,int> pii;
int N, C, F, M;
pii calves[100010];
int sumf[100010], sumb[100010];

int main(){
    scanf("%d%d%d", &N, &C, &F);
    M = N/2;
    for(int i = 0; i < C; i++){
        int a, b; scanf("%d%d", &a, &b);
        calves[i] = pii(a,b);
    }
    sort(calves, calves+C);
    {
        priority_queue<int> que;
        int sum = 0;
        for(int i = 0; i < M; i++){
            que.push(calves[i].second);
            sum += calves[i].second;
            sumf[i] = sum;
        }
        for(int i = M; i < C-M; i++){
            sum += calves[i].second;
            que.push(calves[i].second);
            sum -= que.top(); que.pop();
            sumf[i] = sum;
        }
        while(!que.empty()) que.pop();
        sum = 0;
        for(int i = 0; i < M; i++){
            que.push(calves[C-i-1].second);
            sum += calves[C-i-1].second;
            sumb[C-i-1] = sum;
        }
        for(int i = M; i < C-M; i++){
            sum += calves[C-i-1].second;
            que.push(calves[C-i-1].second);
            sum -= que.top(); que.pop();
            sumb[C-i-1] = sum;
        }
    }
    int ans = -1;
    /*
    for(int i = 0; i < C; i++)
        printf("%d ", calves[i].first);
    puts("");
    for(int i = 0; i < C; i++)
        printf("%d ", calves[i].second);
    puts("");
    for(int i = 0; i < C; i++)
        printf("%d ", sumf[i]);
    puts("");
    for(int i = 0; i < C; i++)
        printf("%d ", sumb[i]);
    puts("");

    for(int i = C-M-1; i >= M; i--){
        printf("%d\n", i);
        if(calves[i].second + sumf[i-1] + sumb[i+1] <= F){
            ans = calves[i].first;
            printf("  %d %d\n", ans, calves[i].second+sumf[i-1]+sumb[i+1]);
        }
    }
    */
    for(int i = C-M-1; i >= M; i--)
        if(calves[i].second + sumf[i-1] + sumb[i+1] <= F){
            ans = calves[i].first;
            break;
        }
    printf("%d\n", ans);
    return 0;
}

Comments