背包（堆动态维护前后缀和 + 二分）

本文主要是介绍背包（堆动态维护前后缀和 + 二分），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接
https://ac.nowcoder.com/acm/problem/17315

思路
题意是从所有物品中选m个出来，使得物品中位数最大，那么可以先将物品组按照价值排序，然后枚举中位数是谁，这里要注意，如果m是奇数，那么直接枚举即可，如过是偶数，那么没办法直接枚举，因为此时中位数有两个，所以m是偶数的时候，可以枚举左边的那个，二分右边的那个。那么怎么判断选了的东西有没有超过背包容量呢？这里可以用前缀和，假设当前枚举到以第i个物品为中位数，那么要从比这个物品小的里面选m / 2个数，比它大的里面选m / 2个数，维护一个堆，当堆的size大于m / 2时，把堆中最占位置的那个拿出来。这样子左右两边都可以贪心的做到最省空间。因为只要中位数是这个数，只需要从左边选出来一些数，右边选出来一些数即可，不需要管价值，此时仅需考虑让背包剩下的空间最多。

代码

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

struct node
{
    int w, v;
    bool operator< (const node& r) const
    {
        return w < r.w;
    }
}s[N];

priority_queue<int> heap;  // 利用堆来动态维护
int l[N], r[N];  // 前缀和和后缀和
int k, n, m;

int main()
{
    cin >> k >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        s[i] = {a, b};
    }
    
    sort(s + 1, s + n + 1);
    
    int left = m / 2, right = m / 2;
    if (m % 2 == 0) left -- ;  // m是偶数的话枚举左中位数算上一个，左边只选m / 2 - 1个
    
    for (int i = 1; i <= n; i ++ )  // 前缀和
    {
        heap.push(s[i].v);
        l[i] = l[i - 1] + s[i].v;
        if (heap.size() > left)
        {
            l[i] -= heap.top();  // 将体积最大的弹出保证背包剩余体积最大
            heap.pop();
        }
    }
    
    while (heap.size()) heap.pop();
    
    for (int i = n; i >= 1; i -- )  // 后缀和
    {
        heap.push(s[i].v);
        r[i] = r[i + 1] + s[i].v;
        if (heap.size() > right)
        {
            r[i] -= heap.top();
            heap.pop();
        }
    }
    
    if (m & 1)  // 从前往后找出最大值
    {
        int now;
        for (int i = left + 1; i <= n - right; i ++ )
            if (l[i - 1] + r[i + 1] + s[i].v <= k) now = s[i].w;
        
        cout << now << endl;
    }
    else  // 枚举左边，二分右边
    {
        int ans = 0;
        for (int i = left + 1; i <= n - right; i ++ )
        {
            int le = i + 1, ri = n - right + 1;
            int now = 0;
            while (le <= ri)
            {
                int mid = le + ri >> 1;
                if (l[i - 1] + r[mid] + s[i].v <= k) now = mid, le = mid + 1;  // 什么时候 + 1
                else ri = mid - 1;
            }
            if (now > i) ans = max(ans, s[i].w + s[now].w);
        }
        
        cout << ans / 2 << endl;
    }
    
    return 0;
}

这篇关于背包（堆动态维护前后缀和 + 二分）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！