共48道题，当前是第41题

初赛真题

01 #include<iostream>
02 #include<algorithm>
03 using namespace std;
04 long int n, k, sum[100001], num = 1, f[100001];
05 struct ren {
06     long int ks, js;
07 };
08 ren z[100001];
09 int cmp(ren a, ren b) {
10     return a.ks > b.ks;
11 }
12 int main() {
13     long int i, j;
14     cin >> n >> k;
15     for (i = 1; i <= k; i++) {
16         cin >> z[i].ks >> z[i].js;
17         sum[z[i].ks]++;
18     }
19     sort(z + 1, z + k + 1, cmp);
20     for (i = n; i >= 1; i--) {
21         if (sum[i] == 0)
22             f[i] = f[i + 1] + 1;
23         else
24             for (j = 1; j <= sum[i]; j++) {
25                 if (f[i + z[num].js] > f[i])
26                     f[i] = f[i + z[num].js];
27                 num++;
28             }
29     }
30     cout << f[1] << endl;
31 }

1. A。
2. B。
3. B。
4. B。
5. B。
6. C。

代码中涉及到了对数字的排序，仔细观察可以看出是一个贪心的过程，按照 $ks$ 属性从大到小依次选择物品。对于代码计算过程比较简单，直接模拟代码计算即可。需要注意的几点是：如果改变第 $20$ 行会导致错误，但是错误是由于调用仍未计算出来的 $f$ 数组导致的，并不会产生数组越界错误。

Question

1. 本程序使用了贪心算法（ ）

2. 第 19 行 sort(z + 1, z + k + 1, cmp); ， sort 排序后 z 数组中的元素按 js 元素降序排序（ ）

3. 以下是对于本代码的一段输入，则对应的输出是 3 （ ）。
15 6
1 2
1 6
4 11
8 5
8 1
11 5

4. 本代码的 20 行 for (i = n; i >= 1; i--) 换成 for (i = 1; i <= n; ++i) ，可能会引发 “数组越界” 错误（ ）

5. 第 9 至 11 行程序定义了一个 cmp 函数以用于 sort 的比较。我们可以用含有以下的一个选项的程序段来定义适用于该结构体类型的小于运算。这个选项是（ ）

6. 本程序的时间复杂度是（ ）