共48道题，当前是第40题

初赛真题

01 #include <cstdio>
02 using namespace std;
03 int n;
04 int a[100];
05 int main() {
06     scanf("%d", &n);
07     for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
08     int ans = 1;
09     for (int i = 1; i <= n; ++i) {
10         if (i > 1 && a[i] < a[i - 1]) ans = i;
11         while (ans < n && a[i] >= a[ans + 1]) ++ans;
12         printf("%d\n", ans);
13     }
14     return 0;
15 }

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

该段代码的作用是找到每个元素后面第一个大于它的元素。在这段代码中进行了一个优化，我们用 $f(i)$ 来表示 $i$ 后面第一个大于 $a_i$ 的元素，那么如果 $a_{i-1} <= a_i$ ，则 $f(i-1) <= f(i)$。这就是这段代码中采取的优化，所枚举到的第一个大于 $a_i$ 的元素的位置 $ans$ 在一般情况下不会清空，而是会从上一次迭代中继承下来，直到遇到 $a[i] < a[i-1]$ 时才会清空。

Question

1. 程序输出的 ans 一定大于 i 。( )

2. 程序输出的 ans 小于等于 n 。( )

3. 若将 if (i > 1 && a[i] < a[i - 1]) 的 < 改为 != 程序输出的结果不会改变。( )

4. 当程序执行到 printf("%d\n", ans); 时，若 ans - i > 2 ，则 a[i+1] <= a[i] 。( )

5. 若输入的 a 数组是一个严格单调递增的数列，此程序的时间复杂度是 ( )

6. 最坏情况下，此程序的时间复杂度为：( )