第 k 天必须完成 k 道题,每套题单只能用一次,求最多能坚持几天。
小杨第 k 天必须完成 k 道题,否则就会偷懒。他有一个题库,含 n 套题单,第 i 套有 aᵢ 道题。
规则:每套题单只能用一次,每天也只能用一套题单,而且不必做完题单里的所有题。
问小杨最多能坚持做题多少天不偷懒。
排序贪心资源分配可用性条件
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个整数 aᵢ |
| 输出 | 最多能坚持的天数 |
| 数据范围 | 1 ≤ n ≤ 10⁶ |
| 数值范围 | 1 ≤ aᵢ ≤ 10⁹ |
| 规则 | 第 k 天需 k 道题;每套题单只用一次;每天只用一套 |
先排序,再依次判断。
| 步骤 | 当前题单 aᵢ | 待满足的天数 | aᵢ ≥ 待满足天数? | 已满足天数 |
|---|---|---|---|---|
| 初始 | — | 第 1 天 | — | 0 |
| 排序后 | 1, 1, 3, 4 | |||
| 第 1 套 | 1 | 第 1 天 | 1 ≥ 1 ✅ | 1 |
| 第 2 套 | 1 | 第 2 天 | 1 ≥ 2 ❌ 跳过 | 1 |
| 第 3 套 | 3 | 第 2 天 | 3 ≥ 2 ✅ | 2 |
| 第 4 套 | 4 | 第 3 天 | 4 ≥ 3 ✅ | 3 |
因为此时待满足的是"第 2 天"
第 2 天需要 2 道题,而这套只有 1 道
而且后面每天需求只增不减,所以这套题单永远都用不上了
❌ 直接跳过
4 套题单理论上能撑 4 天(如果题目数都够)
但要坚持第 4 天需要一套 ≥ 4 的题单
我们已经把 4 用在了第 3 天
而且第 2 天必须用 3(因为 1 不够),所以第 4 天没题单可用了
✅ 最多 3 天
答案 3 ✓
| 数据 | 分析 | 答案 |
|---|---|---|
1 | 第 1 天需要 1 道,这套正好 1 道 | 1 |
1 | 题目说 aᵢ ≥ 1,0 不会出现 | — |
2 | 第 1 天用一套,第 2 天需要 2 道但只剩 1 道 | 1 |
3 | 每天都能满足(1、2、3 都 ≤ 5) | 3 |
3 | 第 1 天用 1、第 2 天用 2、第 3 天用 3 | 3 |
2 | 第 1 天用 2(或第 2 天用 2),最多 | 2 |
aᵢ ≥ k 就能满足第 k 天。读题时这类"不必……"的说明往往是解题的关键。题单升序排序,用"下一个待满足的天数"依次匹配
int cnt = 0; for (每个题单 a) if (a >= cnt + 1) cnt++;——只有三行,因为升序遍历保证了"先用小题单"的贪心选择。二分天数 L,判断能否满足前 L 天
| 方案 | 时间复杂度 | 代码量 |
|---|---|---|
| 排序 + 贪心 | O(n log n) | 约 10 行 |
| 二分答案 | O(n log n) | 约 25 行 |
输入每套题单的题目数,程序会排序后依次匹配天数需求。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long a[1000005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); sort(a, a + n); // 升序:小的题单优先满足小的天数需求 int cnt = 0; // 已能坚持的天数 for (int i = 0; i < n; i++) { // 下一个待满足的是第 cnt+1 天,需要 cnt+1 道题 if (a[i] >= cnt + 1) cnt++; } printf("%d\n", cnt); return 0; }
a[i] < cnt + 1,它连当前最小的需求都满足不了,后面需求只会更大,所以它永远没用,直接跳过是对的。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
sort(a, a + n) | 升序排序 | 保证"先用小题单"的贪心顺序 |
cnt + 1 | 下一个待满足的天数 | cnt 是已满足的天数,下一天就是 cnt+1 |
if (a[i] >= cnt + 1) cnt++; | 贪心匹配 | 够用就用,把大的留给后面 |
long long a[] | 类型 | aᵢ 可达 10⁹,用 long long 更稳 |
a[i] >= cnt(应该是 cnt + 1,因为 cnt 是已满足的天数);③ 用 int 读入 aᵢ(1 ≤ aᵢ ≤ 10⁹,int 边界附近要小心)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 3 | 题面样例 |
1 | 1 | 只有一套 1 道题 |
2 | 1 | 第 2 天需要 2 道,但两套都只有 1 道 |
3 | 3 | 每天需求 1、2、3 都不超过 5 |
3 | 3 | 恰好一一对应 |
2 | 2 | 极大值,考察 long long |
cnt + 1 吗?③ 读入用 long long 了吗?cnt 表示"已满足天数",所以下一个需求是 cnt + 1。aᵢ ≥ k 就够了。需要存 n 个题单的题目数。
✅ n = 10⁶ 时排序约 2000 万次操作,C++ 可以轻松通过。
// 贪心匹配的"需求递增"结构 // 第 k 天需求 k,所以需求序列是 1, 2, 3, ... // 资源 aᵢ 能覆盖需求 k 当且仅当 aᵢ >= k // 排序后用最小的够用资源去满足最小的需求 int cnt = 0; for (int i = 0; i < n; i++) if (a[i] >= cnt + 1) cnt++; // 等价的二分答案写法 bool canDo(int L) { // 能否坚持 L 天 int used = 0; for (int i = 0; i < n && used < L; i++) if (a[i] >= used + 1) used++; return used >= L; } // 然后二分 L 即可(但直接贪心更快) // 这类"需求递增 + 资源可复用一次"的题非常常见
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 递增需求贪心 | 小资源配小需求 | 任务调度、晋升机制、累计型关卡 |
| 可用性条件 | aᵢ ≥ need | 所有"够不够用"的判断 |
| 二分答案 | 把"求最大"变成"判断能否达到" | 单调性问题的通用套路 |
aᵢ 完全等于当天需求,或者允许当天完成"多份题单"——题意会完全不同。这说明"不必做完"这个细节对解法影响极大,读题务必抓准。)