P13750 [NWERC 2024] Limited Library 题解

· · 题解

0x00 省流

有一个 n 层的书架和 m 本书，书架每层有一个高度 a_i，每本书有一个高度 b_i，书可以放进高度不低于书的层，每层最多可以放 x 本书。

你可以往若干层中放入艺术品，放入艺术品的层最多只能放 y（y<x）本书。

求所有书都能放置的前提下最多可以放置多少个艺术品。

特别地，即使不放艺术品也放不下书时，请输出impossible。

0x01 分析

首先我们需要注意到，书架和书的顺序无关紧要。

而且，矮的书可以放入高的层，但高的书不能放入矮的层，所以为了防止占着茅坑不拉屎，我们需要尽量将矮的书放入矮的层，高的书放入高的层，也就是说要将书架和书高度从小到大排序。

于是我们可以得出摆放书的原则：从矮到高、塞满为止。

再来考虑艺术品的问题，我们可以使用贪心策略，将最矮的几层用来放艺术品。

为了防止被罚做 100 道 DP 题，我们来看一下为什么可以贪。

还是那句话，矮的书可以放入高的层，能不能放只取决于高度；然而艺术品放哪都一样，固定消耗 x-y 本书的空间，所以尽量不要放在高的层浪费空间。

等等，题目要求最多的艺术品数量，而我们又拥有了判断 k 个艺术品够不够放的能力，而且 k 个艺术品放不下的话，再多放也是一样放不下。

至此，思路已经明晰了：二分查找。

0x02 实现

Talk is cheap, show me the code!

#include <algorithm>
#include <iostream>
using namespace std;

int n, m, x, y;
int a[100005], b[100005], cnt[100005];

// 判断放 k 个艺术品是否可行
bool check(int k) {
  // 前 k 矮的层用于放艺术品
  for (int i = 1; i <= n; i++) {
    if (i <= k) cnt[i] = y;
    else cnt[i] = x;
  }
  int layer = 1;
  for (int i = 1; i <= m; i++) {
    // 需要换层的情况
    while (layer <= n && (a[layer] < b[i] || !cnt[layer])) layer++;
    // 再放就要 MLE 了……我说的是书架
    if (layer > n) return 0;
    // 把书放到这一层，剩余空间减一
    cnt[layer]--;
  }
  return 1;
}

int main() {
  cin >> n >> m >> x >> y;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= m; i++) cin >> b[i];
  sort(a + 1, a + n + 1);
  sort(b + 1, b + m + 1);
  // 二分查找，要注意边界值
  int l = -1, r = n + 1, mid;
  while (l + 1 < r) {
    mid = l + r >> 1;
    if (check(mid)) l = mid;
    else r = mid;
  }
  // 进食后人 if you WA on #6
  // 存在刚好只够放书不够放艺术品的情况
  if (l >= 0) cout << l;
  else cout << "impossible";
  return 0;
}

写这篇题解的时候这题还是灰题，我个人是建议评黄，一道不错的二分题。