poj2010专题

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

POJ2010 Moo University - Financial Aid

题意:奶牛学校招生,c头奶牛报名,要选n头(n为奇数),学校是义务制,所以每头奶牛的学费都由学校负责。每头奶牛都由自己的考试分数和它需要花的学费,学校总共有f的资金,问合法招生方案中中间分数(即排名第(n+1)/2)最高的是多少。 题解:先将所有的奶牛按照分数由高到低排序,假设k是招的奶牛中排名中间的那头,按照排序可知,[1,k-1]中的奶牛必定被招了(n-1)/2头,[k+1,c]中也必定被招

《挑战程序设计竞赛》3.1.4 二分搜索-最小化第k大的值 POJ2010 3662(2)

POJ2010 http://poj.org/problem?id=2010 题意 给出n个数,要求将这n个数两两相减,把这些相减得到的数排序后,输出位置在中间的那个数。 思路 如果两两相减再排序复杂度太高,肯定超时了,二分法求解复杂度将大大降低。 枚举最中间的那个数,然后判断一下相减得到的数有多少个大于等于枚举的数。 如何判断上面所说的那句呢,其实不用把每个数相减,只需要排序一下,