NC17315 背包(优先队列+很多小知识)

链接：https://ac.nowcoder.com/acm/problem/17315
来源：牛客网

题目描述
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

题解概述

参考的这位大佬，代码是自己写的会有相应的注释，可读性强
https://blog.nowcoder.net/n/598c053c8d1f42db9f626e13c2b23c0e

m<=n<=1e5,v>=1e9
所以很明显不是一个背包问题所以很明显不是一个背包问题
其实仔细一想，中位数也不适合用dp来解决其实仔细一想，中位数也不适合用dp来解决
想找中位数，最好的办法就是排序后枚举每个数想找中位数，最好的办法就是排序后枚举每个数
如果总共是奇数个，左右各取m/2个数如果总共是奇数个，左右各取m/2个数
如果是偶数个，左边取m/2-1,右边取m/2个如果是偶数个，左边取m/2−1,右边取m/2个
中位数就是当前数和右边取的第一个数中位数就是当前数和右边取的第一个数
偶数的情况会比较麻烦，因为中位数不止取决一个数，具体看下面偶数的情况会比较麻烦，因为中位数不止取决一个数，具体看下面

先说左右找数的问题先说左右找数的问题
由于中位数已经确定了，所以想找的数肯定是尽量大小小的由于中位数已经确定了，所以想找的数肯定是尽量大小小的
应该对于每个位置，枚举左右两边大小最小的m/2个数应该对于每个位置，枚举左右两边大小最小的m/2个数
所以就想到了优先队列，优先队列维护已放的大小所以就想到了优先队列，优先队列维护已放的大小
如果发现背包放多了，就去掉其中的最大值如果发现背包放多了，就去掉其中的最大值
这样就可以保证对每个点的左右取到m/2个合理值了这样就可以保证对每个点的左右取到m/2个合理值了
因为只要对于有序数列的某个位置，左右各取相同数，中间一定是中位数因为只要对于有序数列的某个位置，左右各取相同数，中间一定是中位数
然后用优先队列就维护好了两边情况然后用优先队列就维护好了两边情况

然后就是说求法的问题然后就是说求法的问题
奇数很简单，枚举每个位置，如果左右m/2个和中间的大小符合奇数很简单，枚举每个位置，如果左右m/2个和中间的大小符合
那说明这种条件可行，中间的大小就是中位数，取最大即可那说明这种条件可行，中间的大小就是中位数，取最大即可

然后比较麻烦的是偶数，偶数因为偶数不能是枚举的位置决定然后比较麻烦的是偶数，偶数因为偶数不能是枚举的位置决定
偶数需要做的是左边取m/2-1右边m/2个偶数需要做的是左边取m/2−1右边m/2个
所以还要决定的是右边取的第一个所以还要决定的是右边取的第一个
想要中位数最大，肯定也需要右边的那个数尽量大想要中位数最大，肯定也需要右边的那个数尽量大
然而现在这是一个有序数列，右边的第一个数取的越靠右然而现在这是一个有序数列，右边的第一个数取的越靠右
中位数就越大，但是越靠右他的物品总大小一定不会减少中位数就越大，但是越靠右他的物品总大小一定不会减少
可以发现，右边选取物品的总大小是一个递增的可以发现，右边选取物品的总大小是一个递增的
与此同时，他的价值也是递增的，那么可以发现与此同时，他的价值也是递增的，那么可以发现
应该在大小符合的条件下尽量往右选，这就是明显的二分啊应该在大小符合的条件下尽量往右选，这就是明显的二分啊
直接二分右边第一个的位置找到尽量靠右的合法位置即可直接二分右边第一个的位置找到尽量靠右的合法位置即可

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;


typedef long long LL;
const int maxn=100000+7;
LL s1[maxn],s2[maxn];//拿奇数来说 s1 代表前i个数包括i 取m/2个物品其大小的和的最小值，s2代表后i 个数，取m/2个物品其大小的和的最小值
struct Node{
    LL a,b;
    bool operator <(const Node &w)const{
        return a<w.a;
    }
};
Node node[maxn];
priority_queue<LL>q;


int main(){
    int n,m;
    LL v;
    scanf("%lld%d%d",&v,&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%lld%lld",&node[i].a,&node[i].b);
    sort(node+1,node+1+n); //排序
    if(m&1){   //奇数情况时候
        LL ans=0;
        for(int i=1;i<=n;i++){
            s1[i]=s1[i-1]+node[i].b;
            q.push(node[i].b);
            if(q.size()>m/2){s1[i]-=q.top();q.pop();}
        }
        while(!q.empty())q.pop();
        for(int i=n;i;i--){
            s2[i]=s2[i+1]+node[i].b;
            q.push(node[i].b);
            if(q.size()>m/2){s2[i]-=q.top();q.pop();}
        }
        for(int i=m/2+1;i<=n-m/2;i++){//思考为什么从m/2+1开始
            if(node[i].b+s1[i-1]+s2[i+1]<=v)
            ans=max(ans,node[i].a);
        }
        printf("%d\n",ans);
    }
    else {//偶数情况很麻烦
        LL ans=0;
        for(int i=1;i<=n;i++){
            s1[i]=s1[i-1]+node[i].b;
            q.push(node[i].b);
            if(q.size()>m/2-1){s1[i]-=q.top();q.pop();}
        }
        while(!q.empty())q.pop();
        for(int i=n;i;i--){
            s2[i]=s2[i+1]+node[i].b;
            q.push(node[i].b);
            if(q.size()>m/2){s2[i]-=q.top();q.pop();}
        }

        for(int i=m/2;i<=n-m/2;i++){//同理自己思考i的初值
            int l=i+1;
            int r=n-(m/2)+1;
            int mid;
            while(l<=r){//二分逼近，太难了，可能我还比较菜吧
                mid=(l+r)/2;
                if(s2[mid]+s1[i-1]+node[i].b<=v){
                l=mid+1;
                ans=max(ans,(node[i].a+node[mid].a)/2);
            }
                else r=mid-1;
            }
        }
        printf("%lld\n",ans);
    }

    return 0;
}