中位数的题看见一些了，出个专题
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 }
原文：https://www.cnblogs.com/romaLzhih/p/11434518.html