背包

思路：
我们分为奇数和偶数的情况。
如果是奇数，相当于在左右两边各取m/2个数，如果是偶数，左边取m/2-1个，右边取m/2个。
因此，我们先枚举出每一个可能是中位数的数左右两边要取的数的和。首先先对物品按照价值进行排序，然后利用优先队列维护已存物品的体积，如果放的数量超过了要取的数，就去掉占用体积最大的。
最后求的时候，奇数时，枚举每一个数，判断当前数能不能满足背包的大小，然后取最大数就行了。
偶数时，我们枚举左边的那个中位数，然后右边的中位数利用二分来求，因为如果左边的数确定了，那么右边的中位数肯定是越大越好，而我们又是按照物品的价值进行排序的，因此可以直接用二分来查找，只要查找到的数满足背包的大小就代表这个数可以作为右边的中位数。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#define ll long long
#define pi 3.1415927
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;
struct node
{
    ll a,b;
}a[100005];
bool cmp(node x, node y)
{
    return x.a<y.a;
}
priority_queue<ll>q;
ll sum1[100005],sum2[100005];
int main ()
{
    ll T,n,m,i,t,j,k,v,p;
    cin>>v>>n>>m;
    for(i=1;i<=n;++i)
        scanf("%lld %lld",&a[i].a,&a[i].b);
    sort(a+1,a+1+n,cmp);
    k=m/2+(m&1);
    for(i=1;i<=n;++i)
    {
        q.push(a[i].b);
        sum1[i]=sum1[i-1]+a[i].b;
        if(q.size()>k-1)
            sum1[i]-=q.top(),q.pop();
    }
    while (!q.empty())
        q.pop();
    for(i=n;i>0;--i)
    {
        q.push(a[i].b);
        sum2[i]+=sum2[i+1]+a[i].b;
        if(q.size()>k-1)
            sum2[i]-=q.top(),q.pop();
    }

    if(m&1)
    {
        ll res=0;
        for(i=k;i<=n-m/2;++i)
            if(sum1[i-1]+sum2[i+1]+a[i].b<=v)
                res=a[i].a;
        cout<<res<<endl;
    }
    else
    {
        ll res=0;
        for(i=k;i<=n-m/2;++i)
        {
            int l=i+1,r=n-m/2+1;
            while (l<=r)
            {
                ll mid=(l+r)/2;
                if(sum1[i-1]+sum2[mid+1]+a[i].b+a[mid].b<=v)
                    l=mid+1;
                else 
                    r=mid-1;
            }
            if(r>i)
                res=max(res,a[i].a+a[r].a);
        }
        cout<<res/2<<endl;
    }


    return 0;
}