中位数相关

中位数的题看见一些了，出个专题

POJ3669

题意：给出 C 只牛，每只牛有成绩和价钱，要求选 N 只，使这 N 只牛的中位数最大且价钱之和不超过 F

解法：将牛按成绩从小到大排列后依次算出来每只牛前面和后面 N/2 只牛价钱和最小值，用优先队列维护最大值，当队列元素超过 N/2 只的时候减去最大值即可。注意写法。

所以最佳结果就是遍历牛然后选前面+自己+后面最大的那个。

 1 int N, C, F;
 2 int l[MAXN], r[MAXN];
 3 pii cow[MAXN];
 4 priority_queue<int> q;
 5 
 6 int main() {
 7     // freopen("input.txt", "r", stdin);
 8     N = READ(), C = READ(), F = READ();
 9     REP(i, 1, C) cow[i].first = READ(), cow[i].second = READ();
10     sort(cow + 1, cow + 1 + C);
11     int sum = 0, half = N >> 1;
12     REP(i, 1, C) {
13         l[i] = q.size() == half ? sum : INF;
14         sum += cow[i].second;
15         q.push(cow[i].second);
16         if (q.size() > half) {
17             sum -= q.top();
18             q.pop();
19         }
20     }
21     sum = 0;
22     while (!q.empty()) q.pop();
23     PER(i, C, 1) {
24         r[i] = q.size() == half ? sum : INF;
25         sum += cow[i].second;
26         q.push(cow[i].second);
27         if (q.size() > half) {
28             sum -= q.top();
29             q.pop();
30         }
31     }
32     int flag = 0;
33     PER(i, C, 1) {
34         if (l[i] == INF || r[i] == INF) continue;
35         if (l[i] + r[i] + cow[i].second <= F) {
36             flag ^= 1;
37             cout << cow[i].first << endl;
38             break;
39         }
40     }
41     if (!flag) cout << -1 << endl;
42     return 0;
43 }