解题思路

有 m 张 3 分邮票和 n 张 5 分邮票，可以选任意张数（0 张到全部），要找出所有不同的大于 0 的邮资，并从小到大输出。

思路：枚举 + 标记。

1. 枚举取 i 张 3 分邮票（0 到 m）和 j 张 5 分邮票（0 到 n）的所有组合
2. 每种组合的邮资 = 3×i + 5×j
3. 用一个数组标记每种邮资是否出现过（a[sum]++）
4. 最后从小到大扫描，输出所有出现过的大于 0 的邮资

为什么要用数组标记？ 因为不同的邮票组合可能得到相同的邮资（比如 2 张 3 分 = 6 分，但 3 分+5 分=8 分不会重复）。用数组标记就能自动去重，而且下标天然从小到大。

数组开多大？ 邮票最多 100 张 3 分 + 100 张 5 分，最大邮资 = 3×100 + 5×100 = 800，所以数组开到 900 就够了。

参考代码

#include <iostream>
using namespace std;

int a[900], cnt;

int main() {
    int m, n;
    cin >> m >> n;

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            int sum = 3 * i + 5 * j;
            a[sum]++;  // 标记这种邮资出现过
        }
    }

    for (int i = 1; i <= 800; i++) {
        if (a[i] != 0) {
            cout << i << " ";
            cnt++;
        }
    }
    cout << endl << cnt;
    return 0;
}

复杂度分析

• 时间复杂度：O(M×N)，枚举所有邮票组合
• 空间复杂度：O(900)，标记数组