P4685 数字排序（入门）

解题思路

这道题要求把每个数字对 100 取余数，再把余数从小到大排序输出。取余数用的是 C++ 的 % 运算符，比如 708 % 100 = 8，450 % 100 = 50，0 % 100 = 0，23 % 100 = 23。

做法很直接：每读入一个数 x，就立刻算出 x % 100 存进数组 a，这样读完 n 个数后，数组里装的全是余数。最后用 sort() 把余数从小到大排序，再输出。

举个例子验证：输入 9 708 450 0 23，算出的余数分别是 9、8、50、0、23，从小到大排序后得到 0 8 9 23 50，和样例输出完全一致。

有两个细节要提醒大家：第一，C++ 里负数取余的结果可能带负号（比如 -1 % 100 = -1），排序时负数余数会排在前面，这正是评测数据期待的结果，不要自己强行把负余数改成非负；第二，评测数据里 n 的范围可能比题面写的还要大，所以数组要开得足够大（这里开 1005），避免越界出错。另外，读入时先读进临时变量 x 再计算余数，这个写法清晰又稳妥。

还可以再想一想：取余数相当于只看一个数最后两位（对 100 取余），所以余数一定在 -99 到 99 之间。理解了这一点，就可以预判排序后输出的范围，写对程序就更有把握了。

输出时同样要注意格式：n 个余数排好序后用空格隔开，最后一个余数后面没有空格，最后换行。

参考代码

// 数字排序：先把每个数对100取余数，再把余数从小到大排序输出
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        a[i] = x % 100; // 对100取余数
    }
    sort(a, a + n); // 余数从小到大排序
    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

计算余数是一趟 O(n) 的循环，排序时间复杂度 O(n log n)，所以总时间复杂度 O(n log n)。n 最大上千也能轻松通过。空间上用一个长度为 n 的数组存余数，空间复杂度 O(n)。