题解：P4952 [USACO04MAR] Financial Aid

· · 题解

本人的第一篇题解，如果有错请多多包含

题目大意

贝西需要从C头奶牛中选出N头（N为奇数）进入哞哞大学，要求：

  1. 中位数最大化：选出的N头奶牛的CSAT成绩的中位数尽可能大。
  2. 奖学金限制：这些奶牛申请的奖学金总额不能超过F。

如果无法满足条件，输出 -1。

解题思路

关键观察

  1. 中位数的性质：
    • 中位数是排序后位于中间的数（因为N是奇数）。
    • 要使中位数尽可能大，应该尽量选择CSAT成绩高的奶牛。
  2. 奖学金限制：
    • 总奖学金不能超过F，因此需要在保证中位数最大的前提下，尽量选择奖学金少的奶牛。

算法选择

由于直接枚举所有可能的组合计算量太大（C可能达到1e5），我们需要一个高效的算法：

  1. 排序：按CSAT成绩从高到低排序，方便后续处理。
  2. 预处理：
    • 计算前i头奶牛中，最小的 k = (N + 1) / 2 - 1 个奖学金的和（left[i]）。
    • 计算后i头奶牛中，最小的 k 个奖学金的和（right[i]）。
  3. 验证中位数：
    • 遍历每头奶牛，假设它是中位数，检查是否能选出 N 头奶牛满足：
      • 左边至少有 k 头成绩 ≥ 中位数，右边至少有 k 头成绩 ≤ 中位数。
      • 总奖学金 = 中位数奶牛的奖学金 + left[i-1] + right[i+1] ≤ F。

优化方法

不要只看这里

AC代码

#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;
}

复杂度分析