Moo University

题目：http://poj.org/problem?id=2010

题目大意：

奶牛上大学。因为经济问题，每头奶牛都需要一定的补助需求，学校会提供一定的资金用于补助

每头牛都有自己的分数，学校招收的名额也是有限的

题目要求是在录取名额和总补助资金确定的情况下，使得录取学生的成绩的中位数达到最大，问最大的中位数？

思路：

先按分数排个序，从左到右遍历一遍，记录当前位置之前的（名额数/2 ）头奶牛所需的最小补助金额

从右往左遍历一遍，记录当前位置之后的（名额数/2 ）头奶牛所需的最小补助金额。

从后往前走，从（总数-1-名额数/2）地方开始，如果当前补助+前面遍历得到的两个之和不大于总补助金额，那么该位置的分数即为最大中位数。

中间记录时候会进行查找替换，所以选用优先级队列更高效。

比如总共有12头牛，需要5头，那么经过排序以及两次遍历之后，每个位置多出两个量，一个是当前位置之前选出的两头奶牛所需的最小的补助需求金额，另一个量是从当前位置之后选出的两头奶牛所需的最小补助金额。

然后从第10头牛向左遍历，如果当前牛所需的补助加上两个量不大于总补助，那么当前牛的分数即为答案。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAX = 100005;
 7 
 8 class Node
 9 {
10 public:
11     long score, aid;
12     Node(const int a = 0,const int b = 0):score(a),aid(b){ }
13     bool operator<(const Node& rhs)const
14     {
15         return this->aid < rhs.aid;
16     }
17 };
18 
19 bool my_cmp(const Node&lhs, const Node&rhs)
20 {
21     return lhs.score < rhs.score;
22 }
23 
24 Node list[MAX];
25 long mark1[MAX], mark2[MAX];
26 
27 int main()
28 {
29     long N, C, F;
30     scanf("%ld %ld %ld", &N, &C, &F);
31     priority_queue<Node> Q1, Q2;
32     int standard = N / 2, S1 = 0, S2 = 0;
33 
34     for (int i = 0; i < C; i++)
35         scanf("%ld %ld", &list[i].score, &list[i].aid);
36 
37     sort(list, list + C, my_cmp);
38 
39     for (int i = 0; i < C; ++i)
40     {
41         if (i < standard)
42         {
43             Q1.push(list[i]);
44             S1 += list[i].aid;
45             continue;
46         }
47         mark1[i] = S1;
48         if (list[i].aid >= Q1.top().aid)continue;
49         S1 -= Q1.top().aid;
50         Q1.pop();
51         Q1.push(list[i]);
52         S1 += list[i].aid;
53     }
54 
55     for (int i = C - 1; i >= 0; --i)
56     {
57         if (i > C - 1 - standard)
58         {
59             Q2.push(list[i]);
60             S2 += list[i].aid;
61             continue;
62         }
63         mark2[i] = S2;
64         if (list[i].aid >= Q2.top().aid)continue;
65         S2 -= Q2.top().aid;
66         Q2.pop();
67         Q2.push(list[i]);
68         S2 += list[i].aid;
69     }
70     int result = -1;
71     for (int i = C - 1 - standard; i >= standard; i--)
72         if (mark1[i] + mark2[i] + list[i].aid <= F && (result = list[i].score))break;
73     printf("%d
", result);
74     return 0;
75 }

感谢您的阅读，生活愉快~