有好心人路过帮忙看看吗,站外题
  • 板块题目总版
  • 楼主RockyQ012
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/7/6 22:52
  • 上次更新2024/7/7 10:23:52
查看原帖
有好心人路过帮忙看看吗,站外题
1299348
RockyQ012楼主2024/7/6 22:52

问题概述: 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;
}
2024/7/6 22:52
加载中...