GESP 题解库 / 4 级题解 / [GESP202403 四级] 做题 · 第 14 / 25 题
GESP202403 四级 · B3959 · 简单

做题

第 k 天必须完成 k 道题,每套题单只能用一次,求最多能坚持几天。

📊
n ≤ 10⁶
题单数量
🔢
aᵢ ≤ 10⁹
题目数
⚡
O(n log n)
时间复杂度
🎯
排序 + 贪心
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨第 k 天必须完成 k 道题,否则就会偷懒。他有一个题库,含 n 套题单,第 i 套有 aᵢ 道题。

规则:每套题单只能用一次,每天也只能用一套题单,而且不必做完题单里的所有题。

问小杨最多能坚持做题多少天不偷懒。

💡
人话翻译:第 k 天需要从一套题单里挑出至少 k 道题来做。所以一套有 aᵢ 道题的题单,可以用来满足"第 k 天"当且仅当 aᵢ ≥ k。把题单从小到大排序,然后贪心地依次分配即可。

🔍 关键词提取

排序贪心资源分配可用性条件

已知条件

项目说明
输入第一行 n;第二行 n 个整数 aᵢ
输出最多能坚持的天数
数据范围1 ≤ n ≤ 10⁶
数值范围1 ≤ aᵢ ≤ 10⁹
规则第 k 天需 k 道题;每套题单只用一次;每天只用一套

需要解决的问题

02
思维导图
整理解题思路的全貌
📚 排序 + 从最小需求开始配
📥 读入
n ≤ 10⁶
aᵢ 可达 10⁹
用 long long
读入要快(scanf)
🔢 排序
升序排序题单
O(n log n)
n = 10⁶ 也可接受
小题单优先匹配
🎯 贪心分配
cnt = 已满足天数
遍历题单:若 aᵢ ≥ cnt+1
则 cnt 加 1(用它满足第 cnt+1 天)
不够用就跳过该题单
📤 输出
输出 cnt
不需要真的分配哪套给哪天
只需计数
注意边界
03
样例手算推导
样例 4 套题单的分配过程

🧮 样例:n = 4,题单 3 1 4 1,答案 3

先排序,再依次判断。

步骤当前题单 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
1
为什么第 2 套(只有 1 道题)被跳过?

因为此时待满足的是"第 2 天"

第 2 天需要 2 道题,而这套只有 1 道

而且后面每天需求只增不减,所以这套题单永远都用不上了

❌ 直接跳过

2
为什么答案是 3 而不是 4?

4 套题单理论上能撑 4 天(如果题目数都够)

但要坚持第 4 天需要一套 ≥ 4 的题单

我们已经把 4 用在了第 3 天

而且第 2 天必须用 3(因为 1 不够),所以第 4 天没题单可用了

✅ 最多 3 天

答案 3 ✓

🔑
贪心的直觉:天数需求是 1, 2, 3, 4, … 递增的。一套有 aᵢ 道题的题单可以用来满足任何 ≤ aᵢ 的天数需求。所以我们从最小的需求(第 1 天)开始,能用最小的题单就用它,把"容量大"的题单留给后面需求更大的日子。

🧮 几个边界

数据分析答案
1
1
第 1 天需要 1 道,这套正好 1 道1
1
0
题目说 aᵢ ≥ 1,0 不会出现—
2
1 1
第 1 天用一套,第 2 天需要 2 道但只剩 1 道1
3
5 5 5
每天都能满足(1、2、3 都 ≤ 5)3
3
1 2 3
第 1 天用 1、第 2 天用 2、第 3 天用 33
2
2 2
第 1 天用 2(或第 2 天用 2),最多2
⚠️
注意"不必做完"这个条件:很多同学会误以为"题单必须刚好用完才能用",其实题目明确说"不必完成题单内所有的题",所以只要 aᵢ ≥ k 就能满足第 k 天。读题时这类"不必……"的说明往往是解题的关键。
04
解法对比
排序 + 贪心 vs 二分答案

⚔️ 解法对比

🟢 排序 + 贪心(推荐) 推荐

题单升序排序,用"下一个待满足的天数"依次匹配

  • 时间 O(n log n)
  • 一遍扫描即得答案
  • 代码 10 行
  • n = 10⁶ 也轻松
💡
核心实现:int cnt = 0; for (每个题单 a) if (a >= cnt + 1) cnt++;——只有三行,因为升序遍历保证了"先用小题单"的贪心选择。

🟠 二分答案 + 可行性检查

二分天数 L,判断能否满足前 L 天

  • 时间 O(n log n)
  • 额外一个 log 因子
  • 代码更长
  • 不如贪心直接
⚠️
两种思路都对:"判断能否满足前 L 天"这件事也可以用贪心做,于是二分答案也成立。但既然直接贪心一次就能求出最大的 L,没必要再套一层二分。

📈 性能对比

方案时间复杂度代码量
排序 + 贪心O(n log n)约 10 行
二分答案O(n log n)约 25 行
05
算法流程图
排序后依次匹配天数需求
开始读入 n 和 n 个题单题目数 aᵢ把 a 升序排序;cnt = 0依次取出每个题单 aᵢaᵢ ≥ cnt + 1 吗?是 ✓cnt 加 1(满足第 cnt 天)否 ✗跳过该题单所有题单都处理完了吗?输出 cnt结束还有题单 → 继续匹配
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📚 做题天数计算器

输入每套题单的题目数,程序会排序后依次匹配天数需求。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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 边界附近要小心)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
3 1 4 1
3题面样例
1
1
1只有一套 1 道题
2
1 1
1第 2 天需要 2 道,但两套都只有 1 道
3
5 5 5
3每天需求 1、2、3 都不超过 5
3
1 2 3
3恰好一一对应
2
1000000000 1000000000
2极大值,考察 long long
✅
自查清单:① 升序排序了吗?② 判断用的是 cnt + 1 吗?③ 读入用 long long 了吗?

🚨 易错点清单

⚠️
排序方向错:必须升序。降序时会把大容量题单浪费在小需求上。
⚠️
需求量算错:cnt 表示"已满足天数",所以下一个需求是 cnt + 1。
⚠️
误以为题单必须用完:题目明确说"不必完成题单内所有的题",所以 aᵢ ≥ k 就够了。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n)
n 最大
10⁶
运算量
约 2 × 10⁷

时间怎么算的?

空间都用在哪?

需要存 n 个题单的题目数。

✅ n = 10⁶ 时排序约 2000 万次操作,C++ 可以轻松通过。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 贪心匹配的"需求递增"结构
// 第 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ᵢ 完全等于当天需求,或者允许当天完成"多份题单"——题意会完全不同。这说明"不必做完"这个细节对解法影响极大,读题务必抓准。)