Poj 2010: Moo University - Financial Aid

poj2010.md

Poj 2010: Moo University - Financial Aid

題目

分析

Greedy + Priority Queue

參這

根據 score，從大到小遍歷每隻牛。

當遍歷到 cows[i] 時，如果牠的 score 是 median，則此時所需的最少 Financial Aid 為

它左邊 Financial Aid 最少的 (N-1) / 2 隻牛的 Financial Aid 和 +
它右邊 Financial Aid 最少的 (N-1) / 2 隻牛的 Financial Aid 和 +
cows[i] 的 Fiancial Aid

即為：

min_half_of(cows[:i)) + min_half_of(cows(i:]) + cows[i].need

於是，當遍歷到某隻牛 cows[k]，它的

min_half_of(cows[:k)) + min_half_of(cows(k:]) + cows[k].need <= F

那 cows[k].score 就是答案。

實作時，可以使用 priority_queue 並預計算 min_half_of(cows[:i)), min_half_of(cows(i:]) 來加快速度、簡化邏輯。

AC Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

struct Cow {
    ll score;
    ll need;

    bool operator < (const Cow& c) const {
        return score < c.score;
    }
};

const ll INF = 0x3f3f3f3f;

ll N, C, F;
Cow cows[100000];

ll low[100000];
ll high[100000];

ll solve() {
    sort(cows, cows + C);
    const int half = (N-1) / 2;

    // precompute low
    ll total1 = 0;
    priority_queue<ll> pq1;
    for (int i = 0; i < C; i++) {
        if (pq1.size() != half) {
            low[i] = INF;
            pq1.push(cows[i].need);
            total1 += cows[i].need;
            continue;
        }

        low[i] = total1;
        int max_need = pq1.top();
        if (cows[i].need < max_need) {
            pq1.pop();
            total1 -= max_need;
            total1 += cows[i].need;
            pq1.push(cows[i].need);
        }
    }

    // precompute high
    ll total2 = 0;
    priority_queue<ll> pq2;
    for (int i = C - 1; i >= 0; i--) {
        if (pq2.size() != half) {
            high[i] = INF;
            pq2.push(cows[i].need);
            total2 += cows[i].need;
            continue;
        }

        high[i] = total2;
        int max_need = pq2.top();
        if (cows[i].need < max_need) {
            pq2.pop();
            total2 -= max_need;
            total2 += cows[i].need;
            pq2.push(cows[i].need);
        }
    }

    // find the answer
    for (int i = C - 1; i >= 0; i--)
        if (low[i] + high[i] + cows[i].need <= F)
            return cows[i].score;

    return -1;
}

int main() {
    scanf("%lld %lld %lld", &N, &C, &F);
    for (int i = 0; i < C; i++) {
        scanf("%lld %lld", &cows[i].score, &cows[i].need);
    }
    printf("%lld\n", solve());

    return 0;
}