链接：
@[toc]

题目描述

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

输入描述:

第一行三个数v, n, m，分别代表背包容量，物品数量以及需要取出的物品数量 接下来n行，每行两个数ai，bi，分别代表物品价值以及大小 n
≤ 1e5, 1 ≤ m ≤ n, ai ≤ 1e9, v ≤ 1e9, bi ≤ v

输出描述:

仅一行，代表最大的中位数

示例1
输入

20 5 3
3 5
5 6
8 7
10 6
15 10

输出

8

题解：

第一反应感觉是二分
m有奇数偶数两种情况
当m是奇数时，左右分别取m/2个，最中间的就是我们要的答案
当m为偶数时，左边取m/2-1个，右边取m/2个，中位数为两个数，就是当前第i个数和右边第一个数（因为我们枚举时只能选定一个，所以就通过选定第i个把第i+1也确定）
接下来详细讲讲过程
x[i]表示物品最小体积的前缀和
y[]表示物品最小体积的后缀和

对于每一个位置，我们枚举左右两边体积最小的m/2个数，（因为左右两边体积越小，给中间留的越多）
我们可以用优先队列，从小到大依次放入，当背包容量不够时，去掉最大值，依次这样操作，留到最后的就是合理值

当求奇数时，枚举每个位置，如果左右两边m/2个和中间的大小符合条件，则说明满足条件。取最大的中间值

当求偶数时，最终答案是两个数的平均值，我们枚举这两个中左边的数，左边取m/2-1个右边取m/2个。我们的序列是经过排序的，右边的第一个数取的越靠右
中位数就越大，但是越靠右他的物品总大小一定不会减少中位数就越大，但是越靠右他的物品总大小一定不会减少
可以发现，右边选取物品的总大小是一个递增的可以发现，右边选取物品的总大小是一个递增的
与此同时，他的价值也是递增的，那么可以发现与此同时，他的价值也是递增的，那么可以发现应该在大小符合的条件下尽量往右选，这就是明显的二分啊应该在大小符合的条件下尽量往右选，这就是明显的二分，直接二分右边第一个的位置找到尽量靠右的合法位置即可
题解借鉴

代码:

代码是有问题的，但是我看了一阵子也没找出来。。。 

#include<bits/stdc++.h>
const int maxn= 1e5+2;
typedef long long ll;
using namespace std;
struct node{
    ll a,b,id;
}w[maxn];
ll x[maxn],y[maxn];
//x表示前i个数（含第i个）取m/2个物品其大小的和的最小值
//y表示后i个数（含第i个）取m/2个物品其大小的和的最小值 
bool cmp1(node a1,node b1)
{
    return a1.a<b1.a;//按照 价值排序 
}
priority_queue<int>q;
long long int v,n,m;
//v n m
ll solve1(){
    ll sum=0;
    for(int i=m+1;i<=n-m;i++)
    {
        if(x[i-1]+y[i+1]+w[i].b<=v)sum=w[i].a;//枚举中间值，再上左右两边，看看有没有超过背包容量 
        return sum;
    }
}
ll solve2(){
    ll sum=0;
    for(int i=m;i<=n-m;i++){
        int l=i+1;
        int r=n-m+1;
        while(l<=r){//偶数有两个中位数，先确定一个，然后二分另外一个 
            int mid=(r+l)>>1;
            if(x[i-1]+y[mid]+w[i].b<=v)l=mid+1;//如果没超过背包的体积，说明中间值还可以更大 
            else r=mid-1;//否则更小 
        }
        if(r>i)sum=max(sum,w[i].a+w[r].a);//中间两个值和的最大值 
    }
    return sum/2;
}
int main()
{

    cin>>v>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i].a>>w[i].b;
    }
    sort(w+1,w+1+n,cmp1);
    int z=m&1;
    m>>=1;
        for(int i=1;i<=n;i++)
    {
        q.push(w[i].b);
        x[i]=x[i-1]+w[i].b;
        if(q.size()>m-1+z)
        {
            x[i]-=q.top();
            q.pop();
        }

    }
    while(!q.empty())q.pop();
    for(int i=n;i;i--){
        q.push(w[i].b);
        y[i]=y[i+1]+w[i].b;
        if(q.size()>m)
        {
            y[i]-=q.top();
            q.pop();
        }
    }
    if(z)
    {
        cout<<solve1();
    }
    else 
    {
        cout<<solve2();
    }
    return 0;
}