POJ 2010 Moo University Financial Aid(贪心+优先队列)
Description
学校要选出N个人发放助学金,
但有C个人申请(给出C个人的成绩和各自的申请金额),
而且学校只能发放不超过F的金钱,
找出一种策略,使得被发放助学金的学生的群体,
他们的成绩的中位数最大
贪心
按成绩排序作为基本顺序
处理上部:
选取后 N/2 个学生,将每个申请金额置于一个优先级队列中(由大到小),并记下总和
从第 C - N / 2 - 1 个位置当做中位数依次往下测试(保证了选取最大的)
处理下部:
在基本顺序的基础上将下部分(要测试的位置以下)按申请金额由小到大排序
取前 N / 2 个的金额总和,记下最后一个位置(即 int last_pos = N / 2 - 1)
检测:
上部金额 + 下部金额 + 当前检测位置金额 <= F 即退出
否则:
①将当前检测位置 idx 并入上部
②让其前一位置 idx - 1 脱离下部
在对idx - 1这个位置检测
Code
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94