P4645 时间统计（基础）

解题思路

小童每天的学习时长在 1 到 12 小时之间，要求把所有「不少于 3 小时」的时长挑出来，然后从大到小输出。时长不足 3 小时的不参与排序，直接忽略。

**第一步，读懂题意。**读入 n 个学习时长，只输出不小于 3 小时的，并且要从大到小排列。如果时长为 1 或 2 小时，直接丢掉。

**第二步，选择计数排序。**因为学习时长的可能值只有 3、4、5……12 这 10 个，范围特别小，所以用「计数排序」来做：准备 13 个小桶，数组 hourCount[13]，hourCount[hour] 表示学习时长正好是 hour 小时的天数。

**第三步，边读入边筛选。**读入每一天的时长时，如果这个时长大于等于 3，就把它对应的桶加一；小于 3 的直接丢掉。这一步就把「筛选」和「计数」合在一起完成了。

**第四步，倒序输出。**全部读完后，从 12 号桶开始往 3 号桶倒着检查，每个桶里的天数输出多少次，这样输出顺序就自然是从大到小。比如样例 5 8 2 3 1 4 3：小于 3 的 2 和 1 被丢掉，剩下的 5、8、3、4、3 先计数，再倒序输出就是 8 5 4 3 3。

**第五步，确认边界。**题目保证输入的 n 个时长中至少有一个大于等于 3，所以输出一定非空。注意排序范围是从 12 到 3 倒着来，不要写成从 3 到 12，否则就会变成升序。选计数排序而不是快速排序，是因为学习时长的种类很少，用桶统计可以一次搞定筛选和排序，代码更简单也不容易出错。

参考代码

// 统计并按从大到小输出不少于3小时的学习时长
#include <iostream>
using namespace std;

int main() {
    int n; // 天数
    cin >> n; // 读入天数
    int hourCount[13] = {0}; // hourCount[hour]表示学习hour小时的天数
    for (int i = 0; i < n; i++) { // 依次处理每一天
        int hour; // 当前一天的学习时长
        cin >> hour; // 读入学习时长
        if (hour >= 3) { // 只保留不少于3小时的记录
            hourCount[hour]++; // 记录这个时长出现一次
        }
    }
    bool isFirst = true; // 判断是否已经输出过数字
    for (int hour = 12; hour >= 3; hour--) { // 从12小时倒数到3小时
        for (int j = 0; j < hourCount[hour]; j++) { // 输出当前时长的所有记录
            if (!isFirst) { // 不是第一个数字时先输出空格
                cout << ' '; // 输出数字之间的空格
            }
            cout << hour; // 输出当前学习时长
            isFirst = false; // 标记已经输出过数字
        }
    }
    cout << '\n'; // 输出换行
    return 0; // 程序结束
}

复杂度分析

程序先循环 n 次读入并计数，再循环 12 到 3 共 10 个桶输出，时间复杂度是 O(n)。n 最大只有 100，运行时间可以忽略不计。空间上只用了一个长度 13 的计数数组，是 O(1) 的常数空间。