背包 优先队列+二分

题意：找出m个不超过V的最大权值的中位数；
题解：中位数的找法要区别奇偶，奇数直接就是中间，偶数就是中间两边数相加>>1,首先我们要知道如何处理这个问题，先找M>>1,就是先找中位数左右两边的数字，由于我们要找最大的权值，所以我们按照权值升序，在排大小，那么我们是不是就要尽量使两边的大小尽量小，然后，中位数权值尽量大，因为大小是没有顺序的，只是权值有序，所以我们可以扫一次m/2前面前缀，m/2后面后缀，然后这样子是我们在枚举中位数的时候就可以直接枚举终点，想办法把左右两边的大小尽量最小就是，因为权值必然是左边小右边大，所以中间只要满足总大小<V那么就可以随便搞，然后就是奇数直接就可以枚举终点，但是偶数要麻烦一点，我们先找M/2-1，左边的，然后找M/2右边的，必然左边最后一个点是我们需要枚举的，但是仔细观察，我们权值是有序的，是不是可以利用权值有序，使用二分来找右边最合适的呢，答案是肯定的，然后就是注意二分的区间，还有一件事，为什么我的for里面是i是m开始的，然后又要N-M呢，是因为，我前面一半选着M，后面的也选择了m个,所有只可以在M-m-n的区间选择

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<x<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
ll gcd(ll a,ll b)
{
    while(b^=a^=b^=a%=b);
    return a;
}
struct node
{
    int a,b;
    bool operator <(const node d)const
    {
        if(a==d.a) return b<d.b;
        return a<d.a;
    }
};
node ans[maxx];
ll sum1[maxx],sum2[maxx];
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
int main()
{
    int v,m,n;
    cin>>v>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>ans[i].a>>ans[i].b;
    }
    sort(ans+1,ans+1+n);
    int x=m&1;m>>=1;
    priority_queue<ll>q;
    for(int i=1;i<=n;i++)
    {
        q.push(ans[i].b),sum1[i]=sum1[i-1]+ans[i].b;
        if(q.size()>m-1+x) sum1[i]-=q.top(),q.pop();
    }
    while(q.size()) q.pop();
    for(int i=n;i;i--)
    {
        q.push(ans[i].b),sum2[i]=sum2[i+1]+ans[i].b;
        if(q.size()>m) sum2[i]-=q.top(),q.pop();
    }
    int dou=-0x3f3f;
    if(x)
    {
        for(int i=m+1;i<=n-m;i++)
        {
            if(sum1[i-1]+sum2[i+1]+ans[i].b<=v) dou=max(dou,ans[i].a);

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