Description

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

Solution

想起了之前也有道中位数的题，中位数问题可以用堆来优化，这道题要分类讨论，奇偶的情况不太一样
对于中位数，我们可以维护左边 个最少花费和右边 个最少花费，然后遍历取最优
最少花费可以维护一个前缀和与一个后缀和
然后分奇偶

  • 奇数: 直接做
  • 偶数：在奇数的前提下，由于我们对价值排了序，满足单调性，可以二分找到第二个数字

Code

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;

const int N = 1e5 + 5;
struct node {
    long long l, r;
    bool operator < (const node &s) {
        return l < s.l;
    }
}a[N];

long long sum1[N], sum2[N];
int main() {
    long long v; int n, m;
    cin >> v >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + 1 + n);
    long long ans = -1;
    priority_queue<long long> q;
    if(m & 1) {    
        for(int i = 1; i <= n; i++) {
            sum1[i] = sum1[i - 1] + a[i].r; // 维护 m / 2 个小值的最少花费 
            q.push(a[i].r);
            if(q.size() > m / 2) {
                sum1[i] -= q.top(); q.pop();
            }
        }
        while(!q.empty()) q.pop();
        for(int i = n; i >= 1; i--) {
            sum2[i] = sum2[i + 1] + a[i].r;
            q.push(a[i].r);
            if(q.size() > m / 2) {
                sum2[i] -= q.top(); q.pop(); // 维护 m / 2 个大值的最少花费 
            } 
        }
        for(int i = m / 2 + 1; i <= n - m / 2; i++) {
            if(a[i].r + sum1[i - 1] + sum2[i + 1] <= v) {
                ans = max(ans, a[i].l);
            }
        } 
    } else {
        for(int i = 1; i <= n; i++) {
            sum1[i] = sum1[i - 1] + a[i].r;
            q.push(a[i].r);
            if(q.size() > m / 2 - 1) {
                sum1[i] -= q.top(); q.pop();
            }
        }
        while(!q.empty()) q.pop();
        for(int i = n; i >= 1; i--) {
            sum2[i] = sum2[i + 1] + a[i].r;
            q.push(a[i].r);
            if(q.size() > m / 2) {
                sum2[i] -= q.top(); q.pop();
            }
        }
        for(int i = m / 2; i <= n - m / 2; i++) {
            int left = i + 1;
            int right = n - (m / 2) + 1;
            while(left <= right) {
                int mid = left + right >> 1;
                if(sum2[mid] + sum1[i - 1] + a[i].r <= v) { // 注意这里是用 sum2[mid] 细节 
                    left = mid + 1;
                    ans = max(ans, (a[i].l + a[mid].l) / 2);
                } else {
                    right = mid - 1;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}