解题思路

这道题要同时满足两个要求：

1. 每种礼物的数量至少要有 10 个；
2. 每种礼物的数量必须是 4 的倍数。

把两个要求合在一起看，就是：每种礼物的数量必须是一个不小于 10 的 4 的倍数。 4 的倍数从小到大是 4、8、12、16、20、24、28……其中“不小于 10”的最小的那个是 12。 所以不管原来有多少个，补完之后每一种的数量都至少是 12。

现在的问题是：给一个数 x，怎么找到“不小于 x 的、最小的 4 的倍数”？ 可以用公式：t = ((x + 3) / 4) * 4（这里的除法是整除）。

• 先看 x / 4 向下取整，就是 x 里面能装满几组“4 个一组”；
• 加 3 之后再除以 4 做整除，就相当于向上取整，保证至少凑够那一组；
• 最后乘回 4，就得到不小于 x 的最小的 4 的倍数。

我们拿样例的 5 个数逐个验证：

• 8 ：t = ((8+3)/4)4 = 24 = 8，比 10 小，所以补到 12；
• 30 ：t = ((30+3)/4)4 = 84 = 32；
• 12 ：t = ((12+3)/4)4 = 34 = 12，本来就满足，不用补；
• 22 ：t = ((22+3)/4)4 = 64 = 24；
• 18 ：t = ((18+3)/4)4 = 54 = 20。

于是每种礼物补好后的数量依次是：12、32、12、24、20。

最后一步是从大到小排序输出。我们把它们装进数组 a， 先用 sort 从小到大排一遍：12、12、20、24、32， 再用 reverse 把整个数组反过来，变成：32、24、20、12、12，和样例输出完全一致。

参考代码

// P376 补发礼物
// 思路：每种礼物的数量要补成“不小于 x、是 4 的倍数、且至少 10 个”的最小数，
//       最后把所有补好的数从大到小排序输出。
#include <iostream>
#include <algorithm>   // sort 从小到大排序、reverse 反转成从大到小
using namespace std;

int a[105];   // 存每种礼物补好之后的个数

int main() {
    int n;
    cin >> n;   // 读入礼物的种类数

    // 依次读入每种礼物现在的个数
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;   // 第 i 种礼物现在的个数

        // 第一步：算出不小于 x 的最小 4 的倍数
        // ((x + 3) / 4) 是向上取整到几组 4 个，再乘 4 就是对应的 4 的倍数
        int t = ((x + 3) / 4) * 4;

        // 第二步：数量还要求至少 10 个。
        // 4 的倍数里最小的、不小于 10 的是 12，所以不够 12 就补到 12
        if (t < 12) {
            t = 12;
        }

        a[i] = t;   // 记下这种礼物补好后的个数
    }

    // 先从小到大排序
    sort(a, a + n);
    // 再反转，变成从大到小
    reverse(a, a + n);

    // 从大到小输出，数字之间用空格隔开
    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i < n - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

复杂度分析

• 时间：读入并计算每个数的补足结果是 O(1)，一共 n 个数； 排序用 sort，是 O(n log n)。总时间复杂度 O(n log n)，n <= 100 时非常快。
• 空间：只用了一个数组 a 存 n 个数，空间复杂度 O(n)。