专栏文章

P13750 [NWERC 2024] Limited Library 题解

iimnotcfz
P13750题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio68n7g
此快照首次捕获于
2025/12/02 14:02
3 个月前
此快照最后确认于
2025/12/02 14:02
3 个月前
查看原文

0x00 省流

有一个 nn 层的书架和 mm 本书，书架每层有一个高度 aia_i，每本书有一个高度 bib_i，书可以放进高度不低于书的层，每层最多可以放 xx 本书。
你可以往若干层中放入艺术品，放入艺术品的层最多只能放 yy（y<xy<x）本书。
求所有书都能放置的前提下最多可以放置多少个艺术品。
特别地，即使不放艺术品也放不下书时，请输出impossible。

0x01 分析

首先我们需要注意到，书架和书的顺序无关紧要。
而且，矮的书可以放入高的层，但高的书不能放入矮的层，所以为了防止占着茅坑不拉屎，我们需要尽量将矮的书放入矮的层，高的书放入高的层，也就是说要将书架和书高度从小到大排序。
于是我们可以得出摆放书的原则：从矮到高、塞满为止。
再来考虑艺术品的问题，我们可以使用贪心策略，将最矮的几层用来放艺术品。
为了防止被罚做 100 道 DP 题，我们来看一下为什么可以贪。
还是那句话，矮的书可以放入高的层，能不能放只取决于高度；然而艺术品放哪都一样，固定消耗 x−yx-y 本书的空间，所以尽量不要放在高的层浪费空间。
等等，题目要求最多的艺术品数量，而我们又拥有了判断 kk 个艺术品够不够放的能力，而且 kk 个艺术品放不下的话，再多放也是一样放不下。
至此，思路已经明晰了：二分查找。

0x02 实现

Talk is cheap, show me the code!
CPP
#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;
}
写这篇题解的时候这题还是灰题，我个人是建议评黄，一道不错的二分题。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...