题解 | #背包#

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

思路：
堆+二分
虽然题目说是背包但看数据范围1e5的数据明显不符合背包的时间复杂度
并且中位数看着也不像用dp能解决的问题（有后效性）
这时候我们可以这样想，既然我要求最大的中位数
那么我们可以先对价值进行排序
如果m是奇数,即要求所选的物品数量是奇数的时候
我们就可以从后往前扫看符合背包体积及物品数量符合条件的值
对于符合物品数量的条件我们可以利用堆去完成这个条件
如果选的物品数量超过了要求的物品数量的时候就去掉最大的体积的元素
如果符合就是答案
但如果m是偶数的时候就比较麻烦
因为中位数要两个物品，并且这两个物品的价值不一定是相邻的（有可能体积不符合要求）
这个时候找到前面的物品的时候我们再利用二分去找符合条件的并且在最后位置的价值的物品
每次找到都取最大值
这样就能得出结果了
AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct node
{
    ll v,m;
};
node a[100010];
priority_queue<int>q;
int v,n,m;
int le[100010];
int ri[100010];
void pre(int l,int r)
{
    int goods=0;
    int cnt=0;
    for(int i=1; i<=n; i++)//左边要选l个元素
    {
        cnt+=a[i].m;
        q.push(a[i].m);
        goods++;
        if(goods>l)//如果说物品数大于要选的元素，去掉体积最大的元素
        {
            cnt-=q.top();
            q.pop();
            goods--;
        }
        if(goods==l)le[i]=cnt;
    }
    while(!q.empty())q.pop();
    goods=0,cnt=0;
    for(int i=n; i>=1; i--)
    {
        goods++;
        cnt+=a[i].m;
        q.push(a[i].m);
        if(goods>r)
        {
            cnt-=q.top();
            q.pop();
            goods--;
        }
        if(goods==r)ri[i]=cnt;
    }
    return;
}
void deal1()
{
    pre(m/2,m/2);
    for(int i=n; i>=1; i--)
    {
        if(le[i-1]==0||ri[i+1]==0)continue;
        if(a[i].m+le[i-1]+ri[i+1]<=v)
        {
            cout<<a[i].v;
            return;
        }
    }
}
void deal2()
{
    pre(m/2-1,m/2);
    ll ans=0;
    for(int i=m/2; i<=n-m/2; i++)
    {
        int l=i+1,r=n-m/2+1;
        while(l<=r)
        {
            int mid =l+(r-l)/2;
            if(a[i].m+le[i-1]+ri[mid]<=v)l=mid+1;//符合条件就尝试mid往上加
            else r=mid-1;
        }
        if(l-1>=i+1){//我们是要看最后一次l=mid+1的时候mid的值（因为那个时候的mid是符合条件的)
            ans=max(ans,a[i].v+a[l-1].v);
        }
    }
    cout<<ans/2;
    return;
}
int main()
{
    cin>>v>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].v>>a[i].m;
    }
    sort(a+1,a+1+n,[](node b,node c)//先对价值进行排序
    {
        return b.v<c.v;
    });
    if(m%2==1)deal1();
    else deal2();
    return 0;
}