P4655 童童的电脑（基础）

解题思路

第一步，看懂题目。 童童要买一台电脑，去电脑城问了 CPU、内存、硬盘、显示器、主机、键盘、鼠标等 n 件商品的价格（n 不超过 10）。题目要求用"冒泡排序"把价格从大到小排好，再算出这台电脑的总价。

第二步，理解冒泡排序的思路。 冒泡排序是"两两比较，大的往前冒"。一共做 n-1 轮，每一轮从左到右比较相邻的两个数：如果前一个比后一个小，就交换它们的位置。一轮结束后，当前最小的数就被"冒泡"到了最后面；第二轮结束后，第二小的数到了倒数第二位……排完 n-1 轮后，整个数组就是从大到小的顺序。因为它像水里的气泡一样不断往上冒，所以叫冒泡排序。

第三步，顺手算出总价。 总价是把所有价格加起来。可以在读入数据的同时顺便累加，不用再额外扫一遍，这样更省时间。

第四步，用样例验证。 比如样例 899 1200 500 680 1109 125 103，经过冒泡排序后变成 1200 1109 899 680 500 125 103，正好是从大到小。总价则是 899+1200+500+680+1109+125+103=4616。

第五步，注意输出格式。 第一行是排好序的 n 个价格，用空格隔开；第二行是总价，一个整数。两层输出之间用换行分开。

第六步，想一想冒泡的直观画面。 把价格列表竖起来看，价格大的就像泡沫一样往上飘，价格小的往下沉。每一轮比较相邻的两个数，把较小的一直往后交换，就像把一块小石头慢慢沉到水底。轮数越多，排好的部分越多，最后一整列就有序了。因为 n 很小（最多 10 件商品），这种直观但效率一般的排序方法完全够用，也好理解、好记忆。

参考代码

// P4655 童童的电脑：用冒泡排序把价格从大到小排列并计算总价
#include <iostream>
using namespace std;

int price[15];

int main() {
    int n;
    cin >> n;
    int total = 0;
    for (int i = 0; i < n; i++) {
        cin >> price[i];
        total += price[i];
    }
    // 冒泡排序：每一轮把最小的沉到最后
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (price[j] < price[j + 1]) { // 前一个比后一个小就交换，得到从大到小
                int temp = price[j];
                price[j] = price[j + 1];
                price[j + 1] = temp;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << price[i];
    }
    cout << endl;
    cout << total << endl;
    return 0;
}

复杂度分析

冒泡排序要做 n-1 轮，每轮最多比较 n-1 次，所以时间复杂度 O(n²)。n 最大只有 10，最多也就 100 次比较，非常快。总价的累加是 O(n)。空间上只用一个价格数组，O(1)。