NC17315

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

解题思路：

• 中位数取决于中间两个数的大小
• 先对物品根据价值进行排序
• m为奇数时直接枚举中间的那个数，左边选m/2-1个体积最小的，右边选m/2-1个体积最小的
• m为偶数时，考虑枚举右半部分的最小价值，这个最小价值对应了一个最小体积，然后多出来了部分体积，在这部分体积里选择价值最大的，需要用数据结构来维护。
• 对于偶数，维护两个数组L[],R[]。R数组表示从i到n选Rsz个体积最小的物品。L数组表示从0到i选Lsz个物品，且价值最大的是a[i]，对应的最小体积

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
void read(int& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int mod=1e9+7;
const int maxn = 1e6+10;

int n,m,v;
struct node{
    int a,b;//价值，体积
    bool operator<(const node t)const {
        return a<t.a;
    }
}p[maxn];
LL R[maxn], L[maxn];
void init() {
    int Rsz = (m + 1) >> 1, Lsz = m - Rsz;
    priority_queue<int> q;
    q.push(1e9 + 1);
    LL nwsum = 1e9 + 1;
    //R数组表示从i到n选Rsz个体积最小的物品,L数组表示从0到i选Lsz个物品，且体积最大的是i，的最小体积
    fod(i, n, 1) {
        q.push(p[i].b);
        nwsum += p[i].b;
        if (q.size() > Rsz) {
            nwsum -= q.top();q.pop();
            R[i] = nwsum;
        }
        else {
            R[i] = v + 1;
        }
    }

    while (!q.empty()) q.pop();
    q.push(1e9 + 1);
    nwsum = 1e9 + 1;
    fo(i, 1, n) {
        if (q.size() == Lsz) {
            L[i] = nwsum - q.top() + p[i].b;
            q.push(p[i].b);
            nwsum += p[i].b-q.top();
            q.pop();
        } else {
            q.push(p[i].b);
            nwsum += p[i].b;
            L[i] = v + 1;
        }
    }
}


//将体积离散化
LL vb[maxn];
int tot=0;

int mx[maxn];
void up(int root){
    mx[root] = max(mx[root<<1],mx[root<<1|1]);
}
int qu(int root,int l,int r,int R){
    if(r<=R) return mx[root];
    if(l>R) return 0;
    int mid=l+r>>1;
    return max(qu(root<<1,l,mid,R),qu(root<<1|1,mid+1,r,R));
}
void upd(int root,int l,int r,int pos,int v){
    if(l==r) {
        mx[root]=max(mx[root],v);return;
    }
    int mid=l+r>>1;
    if(pos<=mid) upd(root<<1,l,mid,pos,v);
    else upd(root<<1|1,mid+1,r,pos,v);
    up(root);
}

void solve2() {
    //选偶数个的策略是，枚举右边界，在剩余的体积内选择价值最大的
    fo(i, 1, n) {
        if (L[i] <= v) vb[++tot] = L[i];
        if (R[i] <= v) vb[++tot] = R[i];
    }
    sort(vb + 1, vb + 1 + tot);
    tot = unique(vb + 1, vb + 1 + tot) - vb - 1;

    int ans = 0;
    fo(i, 1, n) {
        if (R[i] <= v) {
            int mxv = lower_bound(vb + 1, vb + 1 + tot, v - R[i] + 1) - vb - 1;
            if (mxv >= 1) {
                int lans = qu(1, 1, tot, mxv);//在剩余体积里可以选的最大价值
                ans =max(ans, lans + p[i].a);
            }
        }
        if (L[i] <= v) {
            upd(1, 1, tot, lower_bound(vb + 1, vb + 1 + tot, L[i]) - vb, p[i].a);
        }
    }
    printf("%d\n", ans / 2);
}

void solve1(){
    //选奇数个的策略是，枚举中间点，左边选体积最小的m/2-1个即可
    priority_queue<int>q;
    LL nw= 0;
    int ans=0;
    fo(i,1,n){
        if(nw+R[i]<=v) ans=max(ans,p[i].a);
        q.push(p[i].b);nw+=p[i].b;
        if(q.size()>m/2) nw-=q.top(),q.pop();
    }
    printf("%d\n",ans);
}

int main(){
    read(v);read(n);read(m);
    fo(i,1,n)  read(p[i].a),read(p[i].b);
    sort(p+1,p+1+n);//对价值进行排序
    init();

    if(m==1){
        int  ans = 0;
        fo(i,1,n){
            if(p[i].b<=v) ans=max(ans,p[i].a);
        }
        printf("%d\n",ans);
    }
    else if(m&1) solve1();
    else solve2();
    return 0;
}