网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Jan08]奶牛的选举
成绩 | 0 | 开启时间 | 2013年01月18日 星期五 08:45 |
折扣 | 0.8 | 折扣时间 | 2013年01月18日 星期五 08:45 |
允许迟交 | 是 | 关闭时间 | 2013年01月18日 星期五 08:45 |
输入文件 | elect.in | 输出文件 | elect.out |
在推翻了Farmer John这个残暴的统治者后,奶牛们举行了她们的第一次总统大选,贝茜也是N(1 <= N <= 50,000)头候选奶牛之一。不过,作为一头有远见的奶牛,贝茜想在选举开始前就计算出,哪头奶牛最有可能在竞争中胜出。
选举分两轮进行。第一轮中,得票最多的K(1 <= K <= N)头奶牛晋级到下一轮,在第二轮选举中得票最多的奶牛成为最终的总统。
现在,贝茜告诉了你奶牛i在第一轮投票中的期望得票数A_i(1 <= A_i <= 1,000,000,000)以及她在第二轮投票中的期望得票数B_i(1 <= B_i <= 1,000,000,000)(如果奶牛i能成功晋级的话),她希望你帮她计算一下,如果这些数据无误,那么哪头奶牛将成为总统。任何数值都不会在A_i 列表中出现两次,在B_i列表中也是如此。
程序名: elect
输入格式:
- 第1行: 2个用空格隔开的整数:N 和 K
- 第2..N+1行: 第i+1为2个用空格隔开的整数:A_i 和 B_i
输入样例 (elect.in):
5 3 3 10 9 2 5 6 8 4 6 5
输入说明:
一共有5头奶牛参加选举,在第一轮中得票最多的3头奶牛可以晋级至第二轮。奶牛们在第一轮中的得票期望分别为3,9,5,8,6,第二轮中,分别为10,2,6,4,5。
输出格式:
- 第1行: 输出1个整数,为将被选为总统的奶牛的编号
输出样例 (elect.out):
5
输出说明:
奶牛2,4,5晋级到第二轮。奶牛5在第二轮投票中得到了最多的5票,赢得了选举的最终胜利。