解题思路

老鹰捉小鸡，最高的同学要当“鸡妈妈”，但他没有站在队伍第一个，所以要把最高的同学和站在第一个的同学交换位置。

例如样例：158 140 159 160 144，最高的是 160（在第 4 位），和第一位 158 交换，就变成 160 140 159 158 144，最后再补一个 0 表示结束。

做法分三步：

1. 读入身高：输入以 0 结尾，所以一直读，读到 0 就停下来，存进数组 a，并记下人数 n。
2. 找最高的同学：设一个变量 mx 记录最高的人的下标，一开始假设第 1 个人最高（mx = 0）；然后从第 2 个人开始往后看，遇到比 a[mx] 更高的，就把 mx 改成这个下标。注意用“严格大于”去比较，这样如果有两个同学一样高，会保留最前面的那个。
3. 交换：把 a[0] 和 a[mx] 交换，再依次输出所有人，最后输出 0。

参考代码

// P4431 交换位置：把身高数组中最高的同学和站在第一个的同学交换位置
#include <iostream>
using namespace std;

int main() {
    int a[25];   // 保存身高，学生人数不超过 20，开大一点
    int n = 0;   // 实际人数
    int h;
    while (cin >> h) {      // 一直读身高
        if (h == 0) break;  // 读到 0 表示输入结束
        a[n] = h;
        n++;
    }

    // 找出最高的同学的下标（如果有多个同样高的，取最前面的）
    int mx = 0; // 默认第一个最高
    for (int i = 1; i < n; i++) {
        if (a[i] > a[mx]) mx = i; // 遇到更高的就更新
    }

    // 把最高的和第一个同学交换
    int t = a[0];
    a[0] = a[mx];
    a[mx] = t;

    // 依次输出所有身高，最后再输出 0
    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i < n - 1) cout << " "; // 数字之间用空格隔开
    }
    cout << " 0" << endl; // 最后以 0 结尾
    return 0;
}

复杂度分析

• 找最高的人需要从头到尾扫一遍身高，学生人数最多 20，时间复杂度是 O(n)。
• 只需要一个身高数组，空间复杂度是 O(n)。