解题思路

邮政编码是六位数，前两位决定城市：

• 前两位是 10 → 北京；
• 前两位是 20 → 上海；
• 前两位是 30 → 天津。

怎么取出前两位呢？把六位数除以10000就行了。比如 101400 ÷ 10000 = 10，200030 ÷ 10000 = 20。这里用的是整数除法，除出来的整数部分就是前两位。

题目还要求：同一座城市的信件按原来的顺序输出。所以我们准备三个数组，按读入的先后顺序把邮编放进对应的数组里，这样顺序就保住了。

输出的时候有个小细节：每座城市先打印一行标题（Beijing / Shanghai / Tianjin），再打印一行邮编，邮编之间用空格隔开；如果没有邮编，那一行就空着。为了让末尾没有多余空格，我们采用“第一个直接输出，后面的先在前面补一个空格再输出”的做法。

参考代码

// P4451 邮件分类：按邮政编码前两位分成北京(10)、上海(20)、天津(30)三类，按顺序输出
#include <iostream>
using namespace std;

int bj[10005], sh[10005], tj[10005]; // 三类信件的邮政编码，各存原顺序
int nb, ns, nt;                      // 每类信件的数量

int main() {
    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        int q = x / 10000;     // 六位数除以10000得到前两位
        if (q == 10) bj[nb++] = x;        // 北京
        else if (q == 20) sh[ns++] = x;   // 上海
        else if (q == 30) tj[nt++] = x;   // 天津
    }
    // 输出北京：先打标题，再打邮编（空则空一行）
    cout << "Beijing" << endl;
    for (int i = 0; i < nb; i++) {
        if (i) cout << " ";   // 第一个数前面不加空格
        cout << bj[i];
    }
    cout << endl;
    // 输出上海
    cout << "Shanghai" << endl;
    for (int i = 0; i < ns; i++) {
        if (i) cout << " ";
        cout << sh[i];
    }
    cout << endl;
    // 输出天津
    cout << "Tianjin" << endl;
    for (int i = 0; i < nt; i++) {
        if (i) cout << " ";
        cout << tj[i];
    }
    cout << endl;
    return 0;
}

复杂度分析

• 需要把 n 封信全部读一遍并分类，再各输出一遍，时间复杂度是 O(n)。n 最大 10000，完全没问题。
• 三个数组最多各存 n 个数，空间复杂度是 O(n)。