12982.做题

题目分析

小杨同学按照天数做计划：第1天做1题，第2天做2题，……，第 $k$ 天做 $k$ 题。每天他只能从一套题单中取题（可以只取一部分），且每套题单最多用一次，一旦使用当天即丢弃。当某一天他找不到一套剩余题数不少于当天所需题数的题单时，他就会偷懒，做题计划终止。

我们需要最大化小杨能够坚持的天数。这等同于：合理分配手头的 $n$ 套题单，使得从第1天开始连续满足每天的需求，问最多能连续满足多少天。

解题思路

这是一个典型的贪心问题。

思考：每天的需求是递增的（1, 2, 3, …）。如果我们把题单按题目数量从小到大排序，那么一个直觉的策略是：

• 对于较小的需求，尽量用较小的题单去满足；
• 把较大的题单留给后面更大的需求。

这能保证我们不会浪费大容量的题单。可以严格证明这个贪心策略是正确的：假设存在一个最优方案，没有按照“用最小可行题单”的规则，我们可以通过交换题单的使用顺序，把较小的题单替换当天使用的较大的题单，而较大的题单延后使用，这样一定不会减少总天数。

因此，算法可以这样设计：

1. 将所有题单的题目数从小到大排序。
2. 初始化当前天数 day = 1。
3. 依次遍历排序后的题单，对于每个题单，若其题目数 $a_i \ge \text{day}$，则用这个题单来满足第 day 天的需求，然后 day 自增 1；否则跳过这个题单。
4. 遍历结束后，实际满足的天数为 day - 1。

算法说明

按照上述思路，给出清晰的步骤：

1. 读入 $n$ 和数组 $a$。
2. 对 $a$ 进行升序排序。
3. 设 ans = 0 表示当前已满足的天数。
4. 遍历 $i$ 从 $1$ 到 $n$：
   • 如果 $a_i \ge \text{ans} + 1$，则令 ans = ans + 1（用这个题单满足第 ans+1 天）。
5. 最后输出 ans。

这里 ans 等价于天数 day - 1，因为第 ans 天需要 ans 题，我们在判断时用的是 ans + 1 。

时间复杂度分析

排序需要 $O(n \log n)$ 时间，遍历数组只需 $O(n)$。总时间复杂度为 $O(n \log n)$，空间复杂度 $O(n)$。对于 $n \le 10^6$ 的数据规模，完全可以在 1 秒内完成。

参考代码解析

题目中给出的 C++ 参考代码本质上也是该贪心策略的实现，但写法较为复杂。我们逐步分析：

cpp
复制
1#include<bits/stdc++.h>
2#define maxn 1000006
3using namespace std;
4long long a[maxn];int n;
5int main(){
6    int m,ans=0;
7    cin>>n; m=n; int s=1;
8    for(int i=1;i<=n;i++) {
9        cin>>a[i];
10    }
11    sort(a+1, a+n+1);          // 升序排序
12    for(int j=1; j<=m; j++) {  // j 表示需要满足的天数（需求）
13        for(int k=s; k<=n; k++) { // 从上次找到的位置 s 开始找
14            if(j <= a[k]) {   // 找到第一个题数 ≥ j 的题单
15                ans++;        // 多用一天
16                a[k] = j;     // 标记该题单已使用（赋值为当前天数 j）
17                s = k;        // 记录当前位置，下一次从这儿继续找
18                break;
19            }
20        }
21    }
22    cout << ans;
23    return 0;
24}

代码逻辑解读：

• 外层 j 从 1 递增，表示第 j 天的需求。
• 内层从变量 s 开始，在排序后的数组 a 中寻找第一个满足 a[k] >= j 的题单。
• 找到后，将 ans 加 1，并把该位置的元素修改为 j（相当于“使用”标记，此后该位置不再能满足更大的 j），再将 s 指向当前位置，以备下次查找。
• 变量 s 只会单调右移，因此整个寻找过程相当于用两个指针扫描数组，每找到一个可用题单就消耗它并前进。

时间复杂度：尽管有两层循环，但内层指针 k 从 1 到 n 总共只移动一次，所以寻找过程为 $O(n)$，加上排序 $O(n \log n)$，总体为 $O(n \log n)$。

改进建议：原代码的写法稍显绕弯，且存在一些隐蔽的细节（例如 a[k] = j 改变了原数组值）。实际应用中，直接计数更为简洁。下面给出一个推荐的简洁实现。

简洁参考实现

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    ios::sync_with_stdio(false);
6    cin.tie(nullptr);
7
8    int n;
9    cin >> n;
10    vector<int> a(n);
11    for (int i = 0; i < n; i++) {
12        cin >> a[i];
13    }
14    sort(a.begin(), a.end());  // 升序排序
15
16    int day = 0;  // 已满足的天数
17    for (int x : a) {
18        if (x >= day + 1) {   // 当前题单可以满足下一天
19            day++;
20        }
21    }
22    cout << day << "\n";
23    return 0;
24}

• day 记录已经成功安排的天数，初始为 0。
• 遍历排序后的每个题单 x，若 x >= day + 1，说明可以用它来完成第 day + 1 天的任务，于是 day 加 1。
• 最终 day 即为答案。

该写法思路清晰，易于理解，且常数较小，同样满足时限要求。