共63道题，当前是第53题

Description

1   #include <iostream>
2   using namespace std;
3   int a[101], n, cnt;
4   int main() {
5       cin >> n;
6       for (int i = 1; i <= n; i ++) {
7           cin >> a[i];
8           int j = i;
9           while (j > 1 && a[j] < a[j/2]) {
10              cnt++;
11              int t = a[j];
12              a[j] = a[j/2];
13              a[j/2] = t;
14              j /= 2;
15          }
16      }
17      cout << cnt << endl;
18      return 0;
19  }
假设输入的n是正整数，$a[i]$ 都是在 $[1,n]$ 范围内的整数，完成下面的判断题和单选题：


1. 正确。循环过程中时刻能保证对于任意 $a[i]$，若 $i>1$，则 $a[i/2]<=a[i]$，所以 $a[1]$ 最小。
2. 错误。是能保证 $a[i/2]$ 和 $a[i]$之间的大小关系，所以数组中一些元素的大小关系是无法确定的，比如 $a[2]$ 和 $a[3]$，所以程序并不能保证 $a[1] \sim a[n]$ 是升序的。
3. 正确。可以发现，当 $n$ 个元素按逆序输入时，输出的 $cnt$ 是最大的，不妨设 $a[1]=10,a[2]=9,...,a[10]=1$，可以发现：输入 $a[1]$ 后交换了 $0$ 次、输入 $a[2]$ 后交换了 $1$ 次、输入 $a[3]$ 后交换了 $1$ 次、输入 $a[4]$ 后交换了 $2$ 次、输入 $a[5]$ 后交换了 $2$ 次、输入 $a[6]$ 后交换了 $2$ 次、输入 $a[7]$ 后交换了 $2$ 次、输入 $a[8]$ 后交换了 $3$ 次、输入 $a[9]$ 后交换了 $3$ 次、输入 $a[10]$ 后交换了 $3$ 次。所以总共交换了 $0+1+1+2+2+2+2+3+3+3=19$ 次。 
4. 错误。当 $n$ 个元素按逆序输入时，输出的 $cnt$ 最大，同时对于第 $i$ 个元素 $a[i]$，交换次数为 $⌊log2i⌋-1$ 次。所以： 
对于第 $1$ 个数（共1个数），各交换了0次；
对于第 $2 \sim 3$ 个数（共2个数），各交换了 $1$ 次；
对于第 $4 \sim 7$ 个数（共4个数），各交换了 $2$ 次；
对于第 $8 \sim 15$ 个数（共8个数），各交换了 $3$ 次；
对于第 $16 \sim 31$ 个数（共16个数），各交换了 $4$ 次；
对于第 $32 \sim 63$ 个数（共32个数），各交换了 $5$ 次；
对于第 $64 \sim 100$ 个数（共37个数），各交换了 $6$ 次。
总的交换次数为 $1×0+2×1+4×2+8×3+16×4+32×5+37×6=480$次 $>450$ 次。 
5. D。输入 $a[3](2)$后交换了1次，输入 $a[4](4)$ 后交换了 $1$ 次，输入 $a[5](1)$ 后交换了 $2$ 次，共交换了 $4$ 次。
6. A。只在输入 $a[3](1)$ 后交换了 $1$ 次。 

Question

循环结束时 $a[1]$ 保存的是输入的 $n$ 个数中的最小值。（ ）

循环结束时 $a[1] \sim a[n]$ 按升序排序（即 $a[1]<=a[2]<=...<=a[n]$）。（ ）

当 $n$ 为 $10$ 时，无论输入的 $a[1] \sim a[n]$ 值为多少，输出的 $cnt$ 不会大于 $19$。（ ）

当 $n$ 为 $100$ 时，无论输入的 $a[1] \sim a[n]$值为多少，输出的 $cnt$ 不会大于 $450$。（ ）

当输入的 $n$ 为 $5$，$a[1] \sim a[5]$ 依次为 $3,5,2,4,1$ 时，输出的结果为（ ）。

当输入的 $n$ 为 $5$，$a[1] \sim a[5]$ 依次为 $2,3,1,4,5$ 时，输出的结果为（ ）。