解题思路

妈妈要从 n 家店里挑出三件裙子来买：最便宜的一件、最贵的一件，还有价格排在中间的一件。

怎么找最方便呢？聪明的办法是先把 n 个价格从高到低排好队，就像排队买票一样，排好序后：

• 队头（下标 0）就是最贵的价格；
• 队尾（下标 n-1）就是最便宜的价格；
• 因为题目说 n 是奇数，所以正中间那个（下标 n/2）就是中间价格。

题目要求输出两行：

1. 第一行：所有价格从高到低排好序；
2. 第二行：最便宜的价格、中间价格、最贵的价格。

我们用"选择排序"把价格从大到小排好，再直接按下标输出想要的三个价格就行啦。

打个比方：7个人站成一排，从高到矮排好后，最左边的就是最高的，最右边的就是最矮的，正中间那个就是中等身高的。排好队，答案一眼就能看出来！

参考代码

// P4602 货比n家：价格从高到低排序，再输出最便宜、中间、最贵的价格
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[55];
    for (int i = 0; i < n; i++) cin >> a[i];
    // 选择排序：从高到低排列价格
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[i]) swap(a[i], a[j]);
        }
    }
    // 第一行：由高到低输出所有价格
    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    // 排序后：a[0]最贵，a[n-1]最便宜，中间价在最中间的位置
    cout << a[n - 1] << " " << a[n / 2] << " " << a[0] << endl;
    return 0;
}

复杂度分析

• 选择排序需要比较约 n×(n-1)/2 次，时间复杂度是 O(n²)。本题 n 最大只有 50，非常快。
• 我们用了一个长度为 n 的数组来存价格，空间复杂度是 O(n)。

排序一遍之后，最贵、最便宜、中间价格都可以直接用下标"一眼"取出，非常方便。