avatar
fireworks99
keep hungry keep foolish

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

#include <queue> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct node { int score, money; }; node stu_s[100005];///整体按成绩排序 node stu_m[100005];///下部分按钱排序 bool cmp_score(node a, node b) { if(a.score != b.score) return a.score < b.score; else return a.money < b.money; } bool cmp_money(node a, node b) { return a.money < b.money; } int main() { int N, C, F; scanf("%d%d%d", &N, &C, &F); for(int i = 0; i < C; ++i) { scanf("%d%d", &stu_s[i].score, &stu_s[i].money); stu_m[i].score = stu_s[i].score; stu_m[i].money = stu_s[i].money; } sort(stu_s, stu_s + C, cmp_score); long long up_money = 0; priority_queue<int> up_half_money; for(int i = C - 1, cnt = 0; cnt < (N >> 1); --i, ++cnt) { up_half_money.push(stu_s[i].money); up_money += stu_s[i].money; } for(int i = 0; i < C; ++i) { stu_m[i].score = stu_s[i].score; stu_m[i].money = stu_s[i].money; } sort(stu_m, stu_m + C - N / 2 - 1, cmp_money); long long down_money = 0; int last_score = stu_m[ (N >> 1) - 1 ].score, pos = N / 2 - 1; for(int i = 0; i < (N >> 1); ++i) down_money += stu_m[i].money; int idx = C - 1 - N / 2; while(idx >= 0) { if(up_money + down_money + stu_s[idx].money <= F) break; ///中位数并入上部 if(stu_s[idx].money < up_half_money.top()) { up_money -= up_half_money.top(); up_half_money.pop(); up_half_money.push(stu_s[idx].money); up_money += stu_s[idx].money; } else up_half_money.push(stu_s[idx].money); ///中位数下一个数脱离下部 if(stu_s[idx - 1].score < last_score) { down_money -= stu_s[idx - 1].money; down_money += stu_m[++pos].money; } else; idx --; } if(idx < 0) cout << "-1" << '\n'; else cout << stu_s[idx].score << '\n'; return 0; }
  • 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
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy