题解：P4952 [USACO04MAR] Financial Aid

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

using namespace std;

struct Cow {
    int score;
    int aid;
};

bool compare(const Cow &a, const Cow &b) {
    return a.score > b.score; // 按成绩降序排序
}

int main() {
    int N, C, F;
    cin >> N >> C >> F;

    vector<Cow> cows(C);
    for (int i = 0; i < C; ++i) {
        cin >> cows[i].score >> cows[i].aid;
    }

    sort(cows.begin(), cows.end(), compare); // 排序

    int k = (N + 1) / 2;
    vector<int> left(C, -1);  // left[i] 表示前i头奶牛中最小的k-1个奖学金和
    vector<int> right(C, -1); // right[i] 表示后i头奶牛中最小的k-1个奖学金和

    // 预处理左边的最小奖学金和
    priority_queue<int> max_heap; // 最大堆（堆顶是最大的数）
    int sum = 0;
    for (int i = 0; i < C; ++i) {
        max_heap.push(cows[i].aid);
        sum += cows[i].aid;
        if (max_heap.size() > k - 1) {
            sum -= max_heap.top(); // 移除最大的，保留最小的k-1个
            max_heap.pop();
        }
        if (max_heap.size() == k - 1) {
            left[i] = sum;
        }
    }

    // 预处理右边的最小奖学金和
    while (!max_heap.empty()) max_heap.pop();
    sum = 0;
    for (int i = C - 1; i >= 0; --i) {
        max_heap.push(cows[i].aid);
        sum += cows[i].aid;
        if (max_heap.size() > k - 1) {
            sum -= max_heap.top();
            max_heap.pop();
        }
        if (max_heap.size() == k - 1) {
            right[i] = sum;
        }
    }

    // 遍历寻找最大的中位数
    int max_median = -1;
    for (int i = k - 1; i <= C - k; ++i) {
        if (left[i - 1] != -1 && right[i + 1] != -1) {
            int total = cows[i].aid + left[i - 1] + right[i + 1];
            if (total <= F) {
                max_median = cows[i].score;
                break; // 找到最大的中位数，直接退出
            }
        }
    }

    cout << max_median << endl;

    return 0;
}