poj2010 Moo University

思路：

先按照分数排序，并用大顶堆预处理出每个位置i的左侧最小N/2个花费的和minL[i]以及右侧最小N/2个花费的和minR[i]。

之后在合法范围内从大到小枚举分数中位数，对于某个位置i如果minL[i] + minR[i] + a[i].f <= F，则可行。

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 ll N, C, F, minL[100005], minR[100005];
 9 struct node
10 {
11     ll c, f;
12 };
13 node a[100005];
14 
15 bool cmp(const node & a, const node & b)
16 {
17     return a.c < b.c;
18 }
19 
20 bool check(int i)
21 {
22     return minL[i] + minR[i] + a[i].f <= F;
23 }
24 
25 ll solve()
26 {
27     ll s = 0;
28     priority_queue<ll> q;
29     for (int i = 0; i < C; i++)
30     {
31         if (i < N / 2)
32         {
33             q.push(a[i].f);
34             s += a[i].f;
35         }
36         else
37         {
38             minL[i] = s;
39             if (a[i].f <= q.top())
40             {
41                 s -= q.top();
42                 q.pop();
43                 q.push(a[i].f);
44                 s += a[i].f;
45             }
46         }
47     }
48     s = 0;
49     while (!q.empty())
50     {
51         q.pop();
52     }
53     for (int i = C - 1; i >= 0; i--)
54     {
55         if (i > C - 1 - N / 2)
56         {
57             q.push(a[i].f);
58             s += a[i].f;
59         }
60         else
61         {
62             minR[i] = s;
63             if (a[i].f <= q.top())
64             {
65                 s -= q.top();
66                 q.pop();
67                 q.push(a[i].f);
68                 s += a[i].f;
69             }
70         }
71     }
72     for (int i = C - 1 - N / 2; i >= N / 2; i--)
73     {
74         if (check(i))
75         {
76             return a[i].c;
77         }
78     }
79     return -1;
80 }
81 
82 int main()
83 {
84     while (cin >> N >> C >> F)
85     {
86         for (int i = 0; i < C; i++)
87         {
88             scanf("%I64d %I64d", &a[i].c, &a[i].f);
89         }
90         sort(a, a + C, cmp);
91         cout << solve() << endl;
92     }
93     return 0;
94 }