【每日一题】背包

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

题解
按物品的价值从小到大排序
dp1[i]表示在1到i选m/2个最小的代价，dp2[i]表示在i到n选m/2个最小的代价，用堆处理出dp1，dp2

当m是奇数时，我们把要取的数分成3段取，即前中后， 个数分别为m/2 ，1 ，m/2，比如取7个数， 前取 3 ，中取1 ，后取 3，所以我们可以枚举第一个数这个数，判断

就行了

当m是偶数时我们还是把要取的数分成2段取，即前后，判断

就行了

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[8][2]={-1,0,1,0,0,-1,0,1,1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

ll a[N],b[N],c[N],dp1[N],dp2[N];
bool cmp(int x,int y){
    if(a[x]==a[y])return b[x]<b[y];
    return a[x]<a[y];
}
void solve(){
    ll v,n,m;cin>>v>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++)c[i]=i;
    sort(c+1,c+1+n,cmp);
    priority_queue<int>q;
    for(int i=1;i<=n;i++){
        int x=c[i];
        dp1[i]=dp1[i-1];
        if(i<=m/2)q.push(b[x]),dp1[i]+=b[x];
        if(i>m/2&&b[x]<q.top()){
            dp1[i]+=-q.top()+b[x];
            q.pop(),q.push(b[x]);
        }
    }
    while(!q.empty())q.pop();
    for(int i=n;i>=1;i--){
        int x=c[i];
        dp2[i]=dp2[i+1];
        if(i>n-m/2)q.push(b[x]),dp2[i]+=b[x];
        if(i<=n-m/2&&b[x]<q.top()){
            dp2[i]+=-q.top()+b[x];
            q.pop(),q.push(b[x]);
        }
    }
    ll ans=0;
    if(m&1){
        for(int i=m/2;i<=n-m/2-1;i++){
            if(dp1[i]+dp2[i+2]+b[c[i+1]]<=v)ans=a[c[i+1]];
        }
        cout<<ans;
    }
    else{
        for(int i=m/2;i<=n-m/2;i++){
            if(dp1[i]+dp2[i+1]<=v)ans=(a[c[i]]+a[c[i+1]])/2;
        }
        cout<<ans;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<endl;
    solve();
    return 0;
}