问题概述: Moo大学接受的奶牛数量为奇数N(1≤N≤19999)。 有C头奶牛报考(N≤C≤100000)。 每头奶牛有一个CSAT分数和一个所需的财政补贴数额。学校有限的资金F(0≤F≤2×10^9)用于补贴。 目标是选择N头奶牛,使得它们的CSAT分数的中位数尽可能高。
输入说明: 第1行:三个整数N, C, F,分别代表接受的奶牛数、报考的奶牛数和学校的资金总数。 第2到C+1行:每行两个整数,分别代表一头奶牛的CSAT分数和所需的财政补贴数额。 输出说明:
输出一个整数,表示所选N头奶牛CSAT分数的最大可能中位数。 如果无法选择N头奶牛,则输出-1。
下面是我的代码,咋只有40分呢?
#include <bits/stdc++.h>
using namespace std;
struct cow {
long long grade;
long long money;
}a[100005];
bool cmp1(const cow &a, const cow &b) {
return a.grade > b.grade;
}
long long l[100005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long n, c, f;
cin >> n >> c >> f;
cow a[c + 1];
long long sum = 0;
for (long long i = 1; i <= c; ++i) {
cin >> a[i].grade >> a[i].money;
}
sort(a + 1, a + c + 1, cmp1);
for (long long i = 1; i <= n / 2; ++i) {
sum += a[i].money;
l[i] = sum;
}
long long m = 1;
for (long long i = n / 2 + 1; i <= c; ++i) {
if (sum + a[i].money <= f) {
m = max(m, a[i].grade);
sum += a[i].money;
if (i <= c - n / 2) {
sum -= a[i - n / 2].money;
}
}
}
cout << m << endl;
return 0;
}