贪心算法

1. 代码整体逻辑

题目的核心在于：第 $k$ 天需要做 $k$ 道题。为了让坚持的天数最多，我们应该**“好钢用在刀刃上”，或者说“先易后难”**。

• 第1天只需要1道题，我们应该找题目数量最少且 $\ge 1$ 的题单。
• 第2天需要2道题，我们应该在剩下的题单里找题目数量最少且 $\ge 2$ 的题单。
• 以此类推。

这就是为什么代码中先进行了排序。

2. 逐行解释

• #include <bits/stdc++.h> & using namespace std;

  • 这是竞赛常用的万能头文件，包含了排序、输入输出等所有功能。

• int a[1000005];

  • 定义一个数组 a，用来存储每一套题单里有多少道题。大小开了 100万+，符合题目 $n \le 10^6$ 的要求。

• cin >> n; 和 for 循环输入

  • 读入题单的数量 $n$。
  • 接着读入 $n$ 个整数，存入数组 a 中。

• sort(a+1, a+n+1); <-- 关键步骤

  • 将数组 a 从下标 1 到 $n$ 进行从小到大排序。
  • 目的：把题目少的题单排在前面，优先用来应付要求低的天数（比如第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. 样例模拟验证

输入：

4
3 1 4 1

执行过程：

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。

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int cnt = 0,t1=1;
	for(int i=1;i<=n;i++){
		if(a[i]>=t1){
            t1++;
            cnt++;
        }
	}
    cout<<cnt;
	return 0;
}