链接：https://ac.nowcoder.com/acm/problem/17315 来源：牛客网

Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi 然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大 Applese觉得这个题依然太菜，于是他把这个问题丢给了你 当物品数量为偶数时，中位数即中间两个物品的价值的平均值

本题是要求中位数的n个数中取出m个数的中位数的最大值，并且这m个数的体积和大小还要满足小于背包的体积；

假设要去出k个数，现在已经按价值大小排序，那么就是要在左边取出l个数，右边取出r个数； 当k是奇数时，l = k / 2, r = k / 2; 当k是偶数时，要取出两个数，先确定左边的数，那么还要取出k / 2 - 1个数，右边要取出k / 2个数，另外一个数就是取出的数最靠右的数。

如果取数：先将n个数按价值大小进行排列，假设我们现在已经确定了中位数，就是要求小于中位数的取出的数的体积和大于中位数中取出的数的体积再加上中位数的体积之和是否满足小于背包体积，如果满足就加入到预选答案中。 预处理：处理前i个数当中体积最小的l个数 处理后i个数中体积最小的r个数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

#define int long long
typedef long long LL;
const int N = 100010;
int n, m, k;
LL sum1[N], sum2[N];
priority_queue<int> q;

struct Node{
    int a, b;
    bool operator< (const Node &t) const {
        return a < t.a;
    }
}tr[N];

signed main()
{
    cin >> m >> n >> k;
    int t = k & 1;
    k >>= 1;
    for(int i = 1; i <= n; i ++ ) cin >> tr[i].a >> tr[i].b;
    sort(tr + 1, tr + n + 1);
    
    for(int i = 1; i <= n; i ++ )
    {
        sum1[i] = sum1[i - 1] + tr[i].b;
        q.push(tr[i].b);
        if(q.size() > k - 1 + t) sum1[i] -= q.top(), q.pop();
    }
    
    while(q.size()) q.pop();
    for(int i = n; i; i -- )
    {
        sum2[i] = sum2[i + 1] + tr[i].b;
        q.push(tr[i].b);
        if(q.size() > k) sum2[i] = sum2[i] - q.top(), q.pop();
    }
    
    if(t)
    {
        int ans = 0;
        for(int i = k + 1; i <= n - k; i ++ )
            if(sum1[i - 1] + sum2[i + 1] + tr[i].b <= m) ans = tr[i].a;
        cout << ans << endl;
    }
    else
    {
        int ans = 0;
        for(int i = k; i <= n - k; i ++ )
        {
            int l = i + 1, r = n - k + 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(sum1[i - 1] + sum2[mid] + tr[i].b <= m) l = mid;
                else r = mid - 1;
            }
            if(sum1[i - 1] + sum2[r] + tr[i].b <= m) ans = max(ans, tr[i].a + tr[r].a);
        }
        cout << ans / 2 << endl;
    }
    
    return 0;
}