问题理解

题目描述： Bessie 和她的同伴们成立了一所新的大学，名为 "The University of Wisconsin-Farmside"（简称 "Moo U"）。为了确保入学牛的素质，他们设计了一个非常精确的入学考试，称为 "Cow Scholastic Aptitude Test"（CSAT），分数范围在 1 到 2,000,000,000 之间。

由于学费昂贵，大多数牛都需要财政援助（0 ≤ aid ≤ 100,000）。政府的奖学金有限，因此所有资金必须来自大学有限的基金（总额为 F，0 ≤ F ≤ 2,000,000,000）。

Moo U 只能容纳奇数 N（1 ≤ N ≤ 19,999）头牛，而申请的牛有 C 头（N ≤ C ≤ 100,000）。Bessie 希望录取恰好 N 头牛，以使教育机会最大化，同时使录取牛的中位数 CSAT 分数尽可能高。

输入：

• 第一行：三个整数 N, C, F。
• 接下来的 C 行：每行两个整数，分别表示牛的 CSAT 分数和所需的财政援助金额。

输出：

• 一个整数，表示 Bessie 可以获得的最大中位数 CSAT 分数。如果资金不足以录取 N 头牛，输出 -1。

解决思路

1. 排序：

   • 首先，将所有牛按照 CSAT 分数从高到低排序。这样我们可以方便地选择分数较高的牛。

2. 选择中位数：

   • 中位数的位置是第 ( k = \frac{N}{2} ) 个元素（假设排序是从高到低）。
   • 我们需要确保中位数尽可能高，因此我们需要从高到低选择牛。

3. 财政援助的限制：

   • 我们需要确保所选 N 头牛的财政援助总和不超过 F。
   • 为了最大化中位数，我们需要选择分数较高的牛，同时确保财政援助的总和在限制内。

4. 双端堆优化：

   • 使用两个堆（优先队列）来维护左半部分和右半部分的财政援助总和。
   • 左堆维护前 ( k ) 个最小的财政援助，右堆维护后 ( k ) 个最小的财政援助。
   • 这样可以在 ( O(C \log C) ) 的时间内预处理出所有可能的左和右的财政援助总和。

5. 遍历中位数：

   • 遍历所有可能的中位数位置，计算对应的财政援助总和，找到满足条件的最大中位数。

代码实现

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

using namespace std;

struct Cow {
    int score;
    int aid;
};

bool compareByScore(const Cow &a, const Cow &b) {
    return a.score > b.score;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); // 使用 NULL 代替 nullptr
    
    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(), compareByScore);
    
    int k = N / 2;
    if (C < N) {
        cout << -1 << endl;
        return 0;
    }
    
   
    priority_queue<int> leftHeap;
    int leftTotal = 0;
    vector<int> leftSum(C, 0);
    
    for (int i = 0; i < C; ++i) {
        leftHeap.push(cows[i].aid);
        leftTotal += cows[i].aid;
        if (leftHeap.size() > static_cast<size_t>(k)) { // 使用 static_cast<size_t> 避免警告
            leftTotal -= leftHeap.top();
            leftHeap.pop();
        }
        leftSum[i] = leftTotal;
    }
    
   
    priority_queue<int> rightHeap;
    int rightTotal = 0;
    vector<int> rightSum(C, 0);
    
    for (int i = C - 1; i >= 0; --i) {
        rightHeap.push(cows[i].aid);
        rightTotal += cows[i].aid;
        if (rightHeap.size() > static_cast<size_t>(k)) { // 使用 static_cast<size_t> 避免警告
            rightTotal -= rightHeap.top();
            rightHeap.pop();
        }
        rightSum[i] = rightTotal;
    }
    
    int maxMedian = -1;
    for (int i = k; i < C - k; ++i) {
        int total = leftSum[i - 1] + rightSum[i + 1] + cows[i].aid;
        if (total <= F) {
            maxMedian = cows[i].score;
            break;
        }
    }
    
    cout << maxMedian << endl;
    
    return 0;
}

复杂度分析

• 排序：( O(C \log C) )。
• 预处理左和右的财政援助总和：( O(C \log k) )，因为每次堆操作是 ( O(\log k) )。
• 遍历中位数：( O(C) )。

总的时间复杂度为 ( O(C \log C + C \log k) )，在给定的约束下是可接受的。

示例解释

输入：

3 5 70
30 25
50 21
20 20
5 18
35 30

排序后：

50 21
35 30
30 25
20 20
5 18

中位数位置：

• ( k = 1 )，因此中位数位置是第 1 个元素（从 0 开始计数）。

预处理：

• 左堆：维护前 1 个最小的财政援助。
• 右堆：维护后 1 个最小的财政援助。

遍历中位数：

• 选择中位数为 35，财政援助总和为 18 (5) + 30 (35) + 21 (50) = 69 ≤ 70。

输出：

35

总结

通过排序和双端堆优化，我们能够高效地找到满足财政援助限制的最大中位数 CSAT 分数。这种方法确保了在较大的输入规模下仍然能够高效运行。

反悔贪心

利用贪心计算中位数，相对比较好想，具体看代码

int n, c, f;
PII p[N];
priority_queue<PII > maxp, mc;
priority_queue<PII, vector<PII >, greater<PII > > minp;

void solve()
{
	cin >> n >> c >> f;
	for(int i = 1; i <= c; i ++) cin >> p[i].y >> p[i].x;
	sort(p + 1, p + c + 1); // 现根据钱进行排序
	ll sum = 0;
	// 用堆构造以成绩为中心的中位数
	for(int i = 1; i <= n; i ++){
		PII xx;
		xx.x = p[i].y, xx.y = p[i].x;
		sum += p[i].x;
		if(maxp.empty()) maxp.push(xx);
		else{
			PII t = maxp.top();
			if(xx.x > t.x){
				if(minp.size() < maxp.size()) minp.push(xx);
				else{
					minp.push(xx);
					PII tt = minp.top();
					minp.pop();
					maxp.push(tt);
				}
			}
			else{
				if(minp.size() < maxp.size()){
					maxp.pop();
					minp.push(t);
					maxp.push(xx);
				}
				else maxp.push(xx);
			}
		}
	}
	
	// 要钱最少的前n个人都满足不了肯定就-1了
	if(sum > f){
		cout << -1 << endl;
		return ;
	}
	// res即为当前答案
	PII t = maxp.top();
	int res = t.x;
	// 每次要删掉的只是大顶堆，但是不能根据成绩来删，而是钱，所以再开一个关于钱的大顶堆；
	while(!maxp.empty()){
		t = maxp.top();
		maxp.pop();
		PII xx;
		xx.x = t.y, xx.y = t.x;
		mc.push(xx);
	}
	
	// 判断n之后的人要不要加进来只需要考虑他的成绩是否比中位数大
	// 比中位数数大那么这个人必然要加进来，且中位数必然会更新，但是要删掉的是中间及之前的人中要钱最多的那一位
	for(int i = n + 1; i <= c; i ++){
		PII t = mc.top();
		PII xx;
		xx.x = p[i].y, xx.y = p[i].x;
		if(xx.x > res){
			sum += xx.y;
			minp.push(xx);
			sum -= t.x;
			mc.pop();
			PII tt = minp.top();
			minp.pop();
			xx.x = tt.y, xx.y = tt.x;
			mc.push(xx);
			// 如果加进来发现超标，直接跳出即可
			if(sum <= f) res = tt.x;
			else break;
		}
	}
	
	cout << res << endl;
}