原题链接
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;
}