解题思路

题目在说什么？

n 个同学围成一圈，每个人的身高都不同。我们要找出最高和最矮的同学，让他们互换位置，然后输出新的顺序。

第一步：找出最高和最矮

用“打擂台”的方法，边读边记录：

• mx 记录目前最高的身高，p 记录它的位置（下标）；
• mn 记录目前最矮的身高，q 记录它的位置（下标）。

因为题目保证每个人的身高都不同，所以最高和最矮都是唯一的，不用处理并列的情况。

第二步：交换位置

交换数组里 a[p] 和 a[q] 两个位置的值。交换两个变量要用一个临时变量 t 帮忙：先把 a[p] 存到 t，再把 a[q] 赋给 a[p]，最后把 t 赋给 a[q]。

第三步：输出

交换完成后，从头到尾输出整个数组，中间用空格隔开。

验证样例： 7 个人身高 142 150 132 163 111 149 120，最高 163（位置 4，下标 3），最矮 111（位置 5，下标 4）。交换后变成 142 150 132 111 163 149 120，和输出一致。

参考代码

// P4503 篝火晚会：最高的和最矮的同学互换位置
#include <iostream>
using namespace std;
int main() {
    int n, a[85];
    cin >> n;
    int mx = 0, mn = 201, p = 0, q = 0; // mx最高、mn最矮，p/q记录它们的位置
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > mx) { mx = a[i]; p = i; } // 更新最高
        if (a[i] < mn) { mn = a[i]; q = i; } // 更新最矮
    }
    int t = a[p]; a[p] = a[q]; a[q] = t;      // 交换两人的位置
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

复杂度分析

设有 n 名同学。

• 时间：读入并找最高最矮是一遍循环，交换和输出又是一遍循环，时间复杂度是 O(n)；
• 空间：需要一个能装 n 个身高的数组，空间复杂度是 O(n)。