1. 代码整体逻辑
题目的核心在于:第 kkk 天需要做 kkk 道题。为了让坚持的天数最多,我们应该**“好钢用在刀刃上”,或者说“先易后难”**。
* 第1天只需要1道题,我们应该找题目数量最少且 ≥1\ge 1≥1 的题单。
* 第2天需要2道题,我们应该在剩下的题单里找题目数量最少且 ≥2\ge 2≥2 的题单。
* 以此类推。
这就是为什么代码中先进行了排序。
2. 逐行解释
* #include <bits/stdc++.h> & using namespace std;
* 这是竞赛常用的万能头文件,包含了排序、输入输出等所有功能。
* int a[1000005];
* 定义一个数组 a,用来存储每一套题单里有多少道题。大小开了 100万+,符合题目 n≤106n \le 10^6n≤106 的要求。
* cin >> n; 和 for 循环输入
* 读入题单的数量 nnn。
* 接着读入 nnn 个整数,存入数组 a 中。
* sort(a+1, a+n+1); <-- 关键步骤
* 将数组 a 从下标 1 到 nnn 进行从小到大排序。
* 目的:把题目少的题单排在前面,优先用来应付要求低的天数(比如第1天、第2天)。
* int cnt = 0, t1 = 1;
* cnt:用来记录答案,即坚持了多少天。
* t1:用来记录当前是第几天,同时也代表当天需要做的题目数量(第1天需1道,第2天需2道...初始为1)。
* for(int i=1; i<=n; i++) 循环
* 遍历每一个排好序的题单。
* if(a[i] >= t1) <-- 核心判断
* 判断:当前这个题单的题目数量 (a[i]) 是否大于等于 当天需要的题目数量 (t1)?
* 如果成立(True):说明今天可以用这套题单完成任务。
* t1++:进入下一天,需要的题目数加 1(例如从第1天变成第2天,需求从1变2)。
* cnt++:成功坚持的天数加 1。
* 如果不成立(False):说明这套题单题目太少了,不够今天做的。因为数组是排好序的,后面的题单题目更多,所以直接跳过这套,看下一套(i 会自动增加)。注意:这里 t1 不会增加,因为今天还没完成任务,明天还是得做 t1 道题(或者说今天失败了,代码逻辑其实是“只要找到够做的就当做这一天成功了”)。
* 修正理解:代码逻辑其实是:遍历所有题单,如果能满足当前需求 t1,就算这一天完成了,然后需求升级。如果不能满足,就扔掉这个题单(因为题目说每套只能用一次),继续找下一个更大的题单。
* cout << cnt;
* 输出最终坚持的天数。
3. 样例模拟验证
输入:
执行过程:
1. 排序:数组 a 变为 [1, 1, 3, 4] (下标1~4)。
2. 初始化:cnt = 0 (天数), t1 = 1 (当前需做题数)。
3. 循环 i=1 (a[1]=1):
* 判断 1 >= 1 (成立)。
* t1 变为 2 (明天需要做2道)。
* cnt 变为 1 (坚持了1天)。
4. 循环 i=2 (a[2]=1):
* 判断 1 >= 2 (不成立)。
* 这套题单题目太少,不够做第2天的任务,跳过。
5. 循环 i=3 (a[3]=3):
* 判断 3 >= 2 (成立)。
* t1 变为 3 (明天需要做3道)。
* cnt 变为 2 (坚持了2天)。
6. 循环 i=4 (a[4]=4):
* 判断 4 >= 3 (成立)。
* t1 变为 4 (明天需要做4道)。
* cnt 变为 3 (坚持了3天)。
7. 结束:输出 cnt 即 3。