背包（优先队列/排序）

Slove：
要求价值的中位数，那首先要对价值进行排序，
m为奇数的情况下
然后我们枚举每个位置，如果该位置是中位数的最大，那么这个位置前面选m/2个的重量加上后面m/2个重量，使他们小于V就说明这个位置可以取得的，只需要维护一个大小为m/2 的堆就行，每次pop掉堆中最大的
m为偶数的时候同理
但是中间需要选择两个位置，数据范围为1e5，n^2肯定不行，所以用nlogn的算法，可以枚举第一个位置，二分第二个位置
代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=1e5+7;
const ll mod = 1e9+7;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
struct wmy {
    ll v,w;
} a[maxn];
ll v,n,m,sum1[maxn],sum2[maxn];
bool cmp(wmy x,wmy y) {
    return x.v<y.v;
}
priority_queue<ll>q;
int UpMing() {
    v=read(),n=read(),m=read();
    for(int i=1 ; i<=n ; i++) {
        a[i].v=read();
        a[i].w=read();
    }
    sort(a+1,a+1+n,cmp);
    if(m%2) {
        for(int i=1 ; i<=n ; i++) {
            sum1[i]=sum1[i-1]+a[i].w;
            q.push(a[i].w);
            if(q.size()>m/2) sum1[i]-=q.top(),q.pop();
        }
        while(q.size())  q.pop();
        for(int i=n ; i>=1 ; i--) {
            sum2[i]=sum2[i+1]+a[i].w;
            q.push(a[i].w);
            if(q.size()>m/2) sum2[i]-=q.top(),q.pop();
        }
        ll  ans=-inf;
        for(int i=m/2+1; i<=n-m/2; i++)
            if(sum1[i-1]+sum2[i+1]+a[i].w<=v)
                ans=max(ans,a[i].v);
        out(ans);
    } else {
        for(int i=1 ; i<=n ; i++) {
            sum1[i]=sum1[i-1]+a[i].w;
            q.push(a[i].w);
            if(q.size()>m/2-1) sum1[i]-=q.top(),q.pop();
        }
        while(q.size())  q.pop();
        for(int i=n ; i>=1 ; i--) {
            sum2[i]=sum2[i+1]+a[i].w;
            q.push(a[i].w);
            if(q.size()>m/2-1) sum2[i]-=q.top(),q.pop();
        }
    ll ans=-inf;
        for(int i=m/2-1; i<=n-m/2+1; i++) {
            int l=i+1,r=n-m/2+1;
            while(l<=r) {
                ll mid=(l+r)>>1;
                if(sum2[mid+1]+sum1[i-1]+a[i].w+a[mid].w<=v)
                    ans=max(ans,(a[i].v+a[mid].v)>>1),l=mid+1;
                else r=mid-1;
            }
        }
        out(ans);
    }
    Accept;
}