共48道题，当前是第39题

初赛真题

01 #include<iostream>
02 
03 using namespace std;
04 const int maxn = 100000;
05 int a[maxn], b[maxn], n;
06 int Search(int num, int low, int high) {
07     int mid;
08     while (low <= high) {
09         mid = (low + high) / 2;
10         if (num >= b[mid]) low = mid + 1;
11         else high = mid - 1;
12     }
13     return low;
14 }
15 int main() {
16     int len, pos;
17     cin >> n;
18     for (int i = 1; i <= n; i++)
19         cin >> a[i];
20     b[1] = a[1];
21     len = 1;
22     for (int i = 2; i <= n; i++) {
23         if (a[i] >= b[len]) {
24             len++;
25             b[len] = a[i];
26         } else {
27             pos = Search(a[i], 1, len);
28             b[pos] = a[i];
29         }
30     }
31     cout << len << endl;
32     return 0;
33 }

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

这段代码是在通过输入的数组 a 来构建数组 b ，构建的规则如下：如果 a[i] 大于数组 b 中的最后一个元素，则将其添加到数组 b 后面。否则在数组 b 中通过二分找到第一个大于 a[i] 的值，并将其替换。容易看出，由这样的规则构建的数组 b 是一个单调不减的序列。复杂度为 $O(nlogn)$ ，因为有二分的过程。

Question

1. 输入的 a[i] 必须在 [1,n] 范围内。( )

2. 把第 10 行的 mid + 1 改成 mid 不影响程序运行结果。( )

3. 当数组 a 单调不降时输出为 1 。( )

4. 数组 b 内的元素始终单调不降。( )

5. 当输入第一行为 20 ，第二行为 1 20 2 19 3 18 4 17...9 12 10 11 时，输出为( )

6. 算法的时间复杂度为( )