NC17315 背包

背包

https://ac.nowcoder.com/acm/problem/17315

NC17315 背包

题目地址：

https://ac.nowcoder.com/acm/problem/17315

基本思路：

这道题我们要分类讨论，先看 $m$ 为奇数的情况:

我们考虑先按照物品价值排序物品，那么要找最大中位数就是确定一个位置，如果这个位置能作为中位数，那么也就是说它左边的 $(m-1)/2$ 个物品的最小重量，右边的 $(m-1)/2$ 个物品的最小重量和自身重量的和一定要小于等于背包容量。

我们考虑如何求左边的 $(m-1)/2$ 个物品的最小重量，和右边的 $(m-1)/2$ 个物品的最小重量，这个实际上我们只要使用优先队列优化一下前后缀和，在达到数量的情况下，每次去掉队列里最大的元素就行了。

但是我们看 $m$ 为偶数的情况：

这个情况下我们同样先确定左边 $m/2 - 1$ 个物品的最小重量，和右边 $m/2$ 个物品的最小重量。

但是我们就没办法枚举这个中间位置了，因为中间位置是有两个的，但是这时候实际上我们枚举第一个位置然后二分第二个位置就行了。因为第二个位置对应的数越大中位数肯定也是单调增大的，而且位置越往后最小重量也是递减的，所以符合二分条件，因此二分成立。

ps. 注意一下偶数的情况，算中间两个数平均值时直接向下取整。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 10;
struct Node{
    int val,w;
    bool operator < (const Node & no) const {
      return val < no.val;//按照价值排序;
    }
}a[maxn];
int per[maxn],suf[maxn];
int v,n,m;
signed main() {
  IO;
  cin >> v >> n >> m;
  rep(i, 1, n) cin >> a[i].val >> a[i].w;
  sort(a + 1, a + 1 + n);
  priority_queue<int> que;
  int l = m / 2, r = m / 2;
  if (m % 2 == 0) l--; // 偶数情况左边是m/2-1个;
  //优先队列优化前缀;
  rep(i, 1, n) {
    que.push(a[i].w);
    per[i] = per[i - 1] + a[i].w;
    if (que.size() > l) per[i] -= que.top(), que.pop();
  }
  //优先队列优化后缀;
  while (!que.empty()) que.pop();
  per(i, n, 1) {
    que.push(a[i].w);
    suf[i] = suf[i + 1] + a[i].w;
    if (que.size() > r) suf[i] -= que.top(), que.pop();
  }
  if (m % 2 == 1) {//奇数情况;
    int ans = 0;
    rep(i, l + 1, n - r) {
      if (per[i - 1] + suf[i + 1] + a[i].w <= v) ans = a[i].val;
    }
    cout << ans << '\n';
  } else {//偶数情况;
    int ans = 0;
    rep(i, l + 1, n - r) {
      //二分第二个位置;
      int nl = i + 1, nb = n - r + 1, pos = 0;
      while (nl <= nb) {
        int mid = (nl + nb) >> 1;
        if (per[i - 1] + suf[mid] + a[i].w <= v) pos = mid, nl = mid + 1;
        else nb = mid - 1;
      }
      if (pos > i) ans = max(ans, a[i].val + a[pos].val);
    }
    //注意一下这个要直接向下取整;
    cout << ans / 2 << '\n';
  }
  return 0;
}