POJ 2010: Moo University - Financial Aid

概要

コストa[i]と評価値s[i]の組の列がある．
この中から，N（奇数）個の要素をコストの合計がFを超えないように選び，メディアンを最大化したい．

解法

メディアンはソートしたときの中央値であり，中央の値以外には影響をうけないことを利用する．
N = 2K + 1とする．
コストについてソート．
あるインデックスiについて，iより小さいインデックスの中からK個選ぶときのコストの最小値を計算．iより大きいインデックスについても同様に計算．この計算は，PriorityQueueを用いることでO(N log N)時間で事前に計算できる．
上記二つの値の合計とi番目のコストの合計がF以下であれば，答えをs[i]に更新する．

int N, C, F, K;
pair<int, int> c[100010];
ll l[100010], u[100010];
const ll INF = 1000000000000;
void calc(ll *a){
    ll s = 0LL;
    priority_queue<int> Q;
    for(int i = 0; i < K; ++i){
        Q.push(c[i].second);
        s += c[i].second;
        a[i] = INF;
    }
    for(int i = K; i < C; ++i){
        a[i] = s;
        if(Q.top() > c[i].second){
            s += c[i].second - Q.top();
            Q.pop(); Q.push(c[i].second);
        }
    }
}
int main(){
    scanf("%d%d%d", &N, &C, &F);
    for(int i = 0; i < C; ++i){
        int s, a;
        scanf("%d%d", &s, &a);
        c[i] = make_pair(s, a);
    }
    sort(c, c+C);
    K = N / 2;

    calc(l);
    reverse(c, c+C);
    calc(u);
    reverse(u, u+C);
    reverse(c, c+C);

    int res = -1;
    for(int i = 0; i < C; ++i)
        if(l[i] + u[i] + c[i].second <= F) res = c[i].first;
    printf("%d\n", res);
    return 0;
}