解题思路

队形是什么样子的？

合唱队形要求：中间的同学最高，往两侧身高逐渐降低。现在已经有 n 名学生排好了（n 是偶数）：

• 前一半（第 1 ~ n/2 名）：身高逐个升高；
• 后一半（第 n/2+1 ~ n 名）：身高逐个降低。

还差一名最高的同学要插到队伍正中间。n 个人时正中间是第 n/2+1 个位置，插进去后一共是 n+1 个人，最高的同学正好站在最中间。

怎么实现“插队”？

用数组 a 存原来的 n 名同学，下标从 0 开始，插入位置是 mid = n / 2（也就是第 n/2+1 个位置）。

输出的时候：

1. 依次输出 a[0] 到 a[mid-1]（前半段）；
2. 输出最高的同学 h（插进来的那一位）；
3. 再输出 a[mid] 到 a[n-1]（后半段）。

我们可以用一个循环完成这件事：在循环里，当 i == mid 时，先输出 h，再输出 a[i]，这样 h 就刚好被放在正中间。

验证样例： n=10 时，mid=5，前 5 个是 110 118 123 129 130，接着是 160，再是 131 125 120 115 112，与输出完全一致。

参考代码

// P4502 合唱队形2：把最高的同学插到队伍正中间
#include <iostream>
using namespace std;
int main() {
    int n, a[55], h;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i]; // 读入已站好的n名学生
    cin >> h;                                 // 最高的同学的身高
    int mid = n / 2;                          // 正中间的位置(前半段个数)
    for (int i = 0; i < n; i++) {
        if (i == mid) cout << h << " ";       // 先输出插进来的最高同学
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

设原来有 n 名学生。

• 时间：读入要循环 n 次，输出也要循环 n 次，时间复杂度是 O(n)；
• 空间：需要一个能装 n 名同学身高的数组，空间复杂度是 O(n)。