#P3372. [Usaco2004 Feb]Moo University -- Financial Aid 财政补助

    ID: 2561 传统题 1000ms 512MiB 尝试: 35 已通过: 25 难度: 5 上传者: 标签>难度分类普及+/提高-枚举与搜索枚举中间点排序与序列处理前后缀分解贪心堆贪心删除最差已选项数据结构二叉堆CF1800Green

[Usaco2004 Feb]Moo University -- Financial Aid 财政补助

[USACO 2004 Mar] Moo University - Financial Aid 财政补助

题目描述

贝茜和伙伴们创建了 Moo 大学,设计了奶牛学术能力测试 CSAT 来招收学生。大学学费昂贵,有些奶牛需要学校提供补助。学校可用的补助预算为 FF。共有 CC 头奶牛申请入学,学校必须恰好录取 NN 头,其中 NN 为奇数。

选出的 NN 头奶牛的 CSAT 成绩从小到大排列,排在正中间的成绩就是中位数。例如,3,8,9,7,53,8,9,7,5 的中位数是 77。学校希望在录取者所需补助的总额不超过预算的前提下,让成绩中位数尽可能高。

输入格式

从标准输入读入。第一行是三个整数 N,C,FN,C,F。接下来 CC 行,每行两个整数,依次给出一头奶牛的 CSAT 成绩和她所需的补助额 aa。

输出格式

向标准输出输出一行一个整数,表示可能达到的最大中位数。如果预算无法录取恰好 NN 头奶牛,输出 −1-1。

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

样例解释

录取成绩为 5,35,505,35,50 的奶牛,所需补助共 18+30+21=6918+30+21=69,不超预算。中位数为 3535。

数据范围与约定

NN 为奇数,1≤N≤19 9991\le N\le 19\,999,N≤C≤100 000N\le C\le 100\,000,0≤F≤2×1090\le F\le 2\times 10^9,0≤a≤100 0000\le a\le 100\,000。CSAT 成绩在 11 到 2×1092\times 10^9 之间。