共48道题，当前是第38题

初赛真题

01 #include <iostream>
02 
03 using namespace std;
04 const int maxn = 100005;
05 int n;
06 int a[maxn];
07 int b[maxn];
08 void solve(int l, int r) {
09     if (l == r) return;
10     int mid = (l + r) / 2;
11     solve(l, mid);
12     solve(mid + 1, r);
13     int i = l, j = mid + 1, k = 1;
14         while (i <= mid && j <= r) {
15         if (a[i] <= a[j]) b[k++] = a[i++];
16         else b[k++] = a[j++];
17     }
18     while (i <= mid) b[k++] = a[i++];
19     while (j <= r) b[k++] = a[j++];
20     for (int i = l; i <= r; i++) a[i] = b[i];
21 }
22 int main() {
23     cin >> n;
24     for (int i = 1; i <= n; i++) cin >> a[i];
25     solve(1, n);
26     int ans = 0;
27     for (int i = 1; i <= n; i++) ans = ans + a[i] * i;
28     cout << ans << endl;
29     return 0;
30 }

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

可以看出这段代码时在实现归并排序，在每次归并排序中，首先将区间划分为左右两个子区间，然后再通过双指针 i,j 来将两个子区间进行合并，合并时使用了中间数组 b[i] ，最后在将 b 数组中的值拷贝到 a 中，返回中排序结果。注意最后输出答案时，程序并没有直接输出序列，而是计算 i*a[i] 进行输出。'),

Question

1. 即使 a 中有重复的数字，该程序仍能正常运行并输出正确答案。( )

2. 当运行完 25 行后，a 数组单调不增。( )

3. 当输入如下时，
n
1 2 3 ......n
输出答案为( )

4. 该程序最坏情况下的时间复杂度为( )。

5. 当输入如下时，
5
50 60 30 40 50
输出为( )

6. 下列各组输入获得的答案最大的是( )