514 字
1 分钟
算法笔记 | 贪心与二分的完美结合：Limited Library (NWERC 2024)
1. 题目背景
题目名称：P13750 Limited Library 核心矛盾：
- 书架层数 与新书数量 很大 ()。
- 每层书架有高度限制 。
- 两种状态切换：
- 普通模式：容量为 ，不放艺术品。
- 艺术模式：容量为 ()，额外放一个艺术品。
- 目标：在放下所有书的前提下，最大化“艺术模式”的层数。
2. 思路演进：从 到
❌ 初始尝试：双重循环遍历
最初的想法是模拟填书：先用 容量填书架，填不下的再利用“恢复”出的 空间。
- 瓶颈：嵌套循环处理 数据会导致 次运算，必然 TLE。
- 误区：逐本匹配（Best Fit）在处理带高度限制的“分块装箱”时，实现极其复杂且效率低下。
✅ 最终方案：二分答案 + 策略匹配
观察到“能放置的艺术品数量”具有单调性，因此采用二分搜索。
核心策略 (The “Tallest-to-Tallest” Strategy)
对于确定的艺术品数量 ：
- 资源分配：高书架是“全能资源”。为了让高书（最难处理）能放下，必须把最大的容量 分配给最高的 层书架。
- 分组验证：将书架和书按高度降序排列。
- 第 1 个书架承担前 本书，只需检查这 本书里最高的那本能否放下。
- 第 2 个书架承担接下来的 本，以此类推。
- 处理完 个“普通层”后，剩下的书按每组 本分配给剩余书架。
Why it works? 高书架能放矮书，矮书架不能放高书。将最宝贵的 容量给高书架，能最大化“高度匹配”的成功率。
3. 复杂度分析
- 排序：
- 二分验证：
- 总复杂度：，完美应对 规模。
4. 优化后的代码模板
#include <iostream>#include <vector>#include <algorithm>
using namespace std;
typedef long long ll;
// 验证函数：判断放 k 个艺术品是否可行bool check(int k, int n, int m, int x, int y, const vector<int>& H, const vector<int>& h) { // 快速排除：总槽位不够直接返回 if (1LL * k * y + 1LL * (n - k) * x < m) return false;
int book_ptr = 0; int normal_layers = n - k;
// 优先处理容量为 x 的高书架 for (int i = 0; i < normal_layers; ++i) { if (book_ptr >= m) return true; if (H[i] < h[book_ptr]) return false; // 最高的书架放不下最高的那组书 book_ptr += x; }
// 处理容量为 y 的矮书架 for (int i = normal_layers; i < n; ++i) { if (book_ptr >= m) return true; if (H[i] < h[book_ptr]) return false; book_ptr += y; }
return book_ptr >= m;}
int main() { ios::sync_with_stdio(false); cin.tie(0);
int n, m, x, y; cin >> n >> m >> x >> y; vector<int> H(n), h(m); for (int &i : H) cin >> i; for (int &i : h) cin >> i;
// 关键：降序排序 sort(H.begin(), H.end(), greater<int>()); sort(h.begin(), h.end(), greater<int>());
// 预判：若 0 个艺术品都放不下，则 Impossible if (!check(0, n, m, x, y, H, h)) { cout << "impossible" << endl; return 0; }
int low = 0, high = n, ans = 0; while (low <= high) { int mid = low + (high - low) / 2; if (check(mid, n, m, x, y, H, h)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } cout << ans << endl; return 0;} 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
算法笔记 | 贪心与二分的完美结合：Limited Library (NWERC 2024)
https://caoyue.xin/posts/test/2026-04-27-limited-library/ 部分信息可能已经过时
相关文章 智能推荐