解题思路

这道题可以分成三步想：

第一步：找到最高的同学和最低的同学。 我们一边读入身高，一边记录"目前最高的是第几个"和"目前最矮的是第几个"。用两个变量 maxp 和 minp 记住它们的位置（下标）。就像比赛时裁判记住谁暂时领先一样，每读一个新身高就比一比、换一换。

第二步：看看题目给的两个条件。

1. 最高和最矮不相邻 —— 说明中间至少有一位同学；
2. 最高在最矮前面 —— 说明最高的下标一定小于最矮的下标。

有了这两个条件，中间的同学就是 maxp+1 到 minp-1 这些位置上的同学，直接用一个 for 循环输出就行。

第三步：注意学号从1开始。 数组下标是从0开始的，而学号是从1开始的，所以输出的时候下标要加1：i+1 才是学号。

打个比方：就像一排小朋友排队，最高的小朋友站在前面，最矮的站在后面，我们要找出夹在中间的所有小朋友，并喊出他们的学号和身高。

参考代码

// P4472 中间同学的身高：找出最高和最矮，输出二者之间（按输入顺序）所有同学的学号与身高
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[1005];      // 按学号顺序存身高
    int maxp = 0;     // 最高同学的位置
    int minp = 0;     // 最矮同学的位置
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > a[maxp]) maxp = i;  // 比目前最高的还高，更新最高
        if (a[i] < a[minp]) minp = i;  // 比目前最矮的还矮，更新最矮
    }
    // 题目保证最高在最矮前面，直接输出二者之间的同学（不含端点）
    for (int i = maxp + 1; i < minp; i++) {
        cout << (i + 1) << ' ' << a[i] << endl;  // 学号 = 下标+1
    }
    return 0;
}

复杂度分析

• 时间：第一遍读入找最高最矮是 O(n)，第二遍输出中间同学最多也是 O(n)，合起来还是 O(n)。
• 空间：用了一个数组存 n 个身高，是 O(n)。