MaskAllocation - 题解

标签与难度

标签: 数论, 构造, 欧几里得算法, 贪心, 递归难度: 1700

题目大意喵~

Miiina-san, konnichiwa! 你们好呀，我是你们的解题我，喵~ 🐾

这道题是说，我们收到了 $n \times m$ 个非常珍贵的口罩，需要把它们分装到一些盒子里。这些盒子必须满足一个非常神奇的条件：

它们可以被精确地分成 $m$ 堆，并且每一堆里面的口罩总数都正好是 $n$ 。
同时，同一批盒子，也可以被精确地分成 $n$ 堆，并且每一堆的口罩总数都正好是 $m$ 。

我们的任务有两个，呐：

找到一种分装方案，使得使用的盒子总数最少。
在所有盒子数最少的方案中，找到一个方案，其盒子大小组成的序列的字典序最大。

字典序最大就是说，如果我们把盒子大小从大到小排列，我们希望尺寸大的盒子数量尽可能多，并且排在最前面。比如说，序列 [5, 4, 3] 就比 [5, 3, 4] 的字典序大哦！

解题思路分析

呜喵~ 这道题看起来像一个复杂的组合和划分问题，对吧？但其实，它背后藏着一个非常经典和优美的数学思想，就像猫咪优雅的步伐一样，喵！

问题的核心是找到一个数字集合（也就是每盒口罩的数量），这个集合既能凑成 $m$ 个 $n$ ，也能凑成 $n$ 个 $m$ 。总口罩数是 $n \times m$ 。

让我们先来想一个简单的情况。如果 $n$ 是 $m$ 的倍数，比如说 $n=6, m=3$ 。总共有 18 个口罩。我们需要：

分成 3 堆，每堆 6 个。
分成 6 堆，每堆 3 个。

最简单的方案是什么呢？我们可以准备 6 个盒子，每个盒子里都放 3 个口罩。

检查条件1：需要 3 堆，每堆 6 个。我们可以把 6 个盒子两两一组，(3,3), (3,3), (3,3)，这样就凑成了 3 堆，每堆都是 6。成功！
检查条件2：需要 6 堆，每堆 3 个。我们每个盒子本身就是一堆，正好 6 堆。也成功了！

这个思路很棒！当 $n$ 是 $m$ 的倍数时（假设 $n \ge m$ ），我们可以用 $n$ 个大小为 $m$ 的盒子来解决问题。

那如果 $n$ 不是 $m$ 的倍数呢？比如 $n=5, m=3$ 。这里就要请出我们的大救星——**欧几里得算法（辗转相除法）**了，喵！

我们可以把这个问题想象成用正方形瓷砖铺满一个 $n \times m$ 的大矩形。每一个正方形瓷砖就代表一类盒子，瓷砖的边长就是盒子的大小。为什么可以这样想呢？因为一个完美的平铺方案，保证了每一行（总长 $m$ ）和每一列（总长 $n$ ）都被瓷砖恰好覆盖。这就和我们的分组要求不谋而合了！

用欧几里得算法的思想来解决这个问题，过程是这样的（我们假设 $n \ge m$ ）：

第一步： 我们可以把 $n$ 分解成 $n = k \cdot m + r$ ，其中 $k = \lfloor n/m \rfloor$ 是商， $r = n \pmod m$ 是余数。这启发我们将问题分解。我们可以先处理 $k \cdot m \times m$ 的部分，剩下的就是一个 $r \times m$ 的子问题。
构造解： 我们提出一个构造方案：对于 $(n, m)$ 的问题，我们的盒子集合 $S(n, m)$ 由两部分组成：
- 第一部分： $(n - r)$ 个大小为 $m$ 的盒子。因为 $n-r = k \cdot m$ ，所以就是 $k \cdot m$ 个大小为 $m$ 的盒子。
- 第二部分：解决子问题 $(m, r)$ 所需的盒子集合 $S(m, r)$ 。
证明这个构造是正确的（归纳法~喵）：
- 归纳基础： 当 $r=0$ 时， $m$ 整除 $n$ 。 $n=k \cdot m$ 。我们的方案是 $k \cdot m = n$ 个大小为 $m$ 的盒子。这在开头已经验证过是可行的啦。
- 归纳假设： 假设我们已经知道如何为子问题 $(m, r)$ 构造一个满足条件的盒子集 $S(m, r)$ 。它能被分成 $m$ 组（每组和为 $r$ ）和 $r$ 组（每组和为 $m$ ）。
- 归纳步骤： 现在我们来验证为 $(n, m)$ $(n, m)$ 构造的集合 $S(n, m) = \{m, \dots, m\} \text{ (k} \cdot \text{m 个)} \cup S(m, r)$ $S (n, m) = {m, \dots, m} (k \cdot m 个) \cup S (m, r)$ 是否满足条件。
  - 凑成 $m$ 组，每组和为 $n$ ： 我们有 $k \cdot m$ 个大小为 $m$ 的盒子，可以把它们平均分成 $m$ 组，每组有 $k$ 个盒子，和为 $k \cdot m$ 。根据归纳假设， $S(m, r)$ 可以分成 $m$ 组，每组和为 $r$ 。现在，我们把这两部分配对！从第一部分取一组（和为 $k \cdot m$ ），从第二部分取一组（和为 $r$ ），加起来就是 $k \cdot m + r = n$ ！因为两部分都能分成 $m$ 组，所以我们正好能凑出 $m$ 组和为 $n$ 的大组。完美！
  - 凑成 $n$ 组，每组和为 $m$ ： 我们需要 $n = k \cdot m + r$ 组。我们手头有 $k \cdot m$ 个大小为 $m$ 的盒子，它们自己就可以形成 $k \cdot m$ 组，每组和为 $m$ 。还差 $r$ 组呢？别忘了我们还有 $S(m, r)$ ！根据归纳假设， $S(m, r)$ 正好可以分成 $r$ 组，每组的和为 $m$ 。把这两部分合起来，我们总共就有了 $k \cdot m + r = n$ 组和为 $m$ 的分组！也成功了！

这个过程不断重复，就像辗转相除一样，直到余数为0。每一步我们都生成一些盒子。

关于最优性：

盒子数最少：这个构造是基于贪心思想。在每一步，我们都尽可能使用当前尺寸下最大的盒子（比如对于 $(n,m)$ ，我们使用尺寸为 $m$ 的盒子）。这种贪心策略恰好能得到最优解。
字典序最大：我们的算法总是先生成较大尺寸的盒子（先是 $m$ ，然后是 $r_1, r_2, \dots$ ）。所以只要按生成的顺序输出，自然就满足字典序最大的要求啦！

总结一下，算法流程就是：

输入 $n, m$ 。不妨让 $n$ 始终大于等于 $m$ 。
当 $m$ $m$ 不为 0 时：
- 计算 $k = n / m$ 和 $r = n \% m$ 。
- 我们生成 $k \times m$ 个大小为 $m$ 的盒子。
- 将问题规模缩小为 $(m, r)$ ，即令 $n=m, m=r$ 。
重复此过程，直到 $m$ 变为 0。将所有生成的盒子大小输出即可。

代码实现

这是我根据上面的思路，精心为你准备的一份C++代码哦！注释超详细的，快来看看吧~ 喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 我的小助手函数，用来处理单次测试用例喵~
void solve() {
    long long n, m;
    std::cin >> n >> m;

    // 为了方便处理，我们始终让 n >= m
    if (n < m) {
        std::swap(n, m);
    }

    // 用一个 vector<pair> 来存储 {盒子大小, 盒子数量}
    // 这样可以避免生成一个超大的数组，更高效哦！
    std::vector<std::pair<long long, long long>> box_groups;
    long long total_boxes = 0;

    // 这是欧几里得算法的核心循环，喵~
    while (m > 0) {
        // n = k * m + r
        // 我们要生成 k * m 个大小为 m 的盒子
        // 这里的 k * m 就是 n - (n % m)
        long long num_of_m_sized_boxes = n - (n % m);
        
        if (num_of_m_sized_boxes > 0) {
            box_groups.push_back({m, num_of_m_sized_boxes});
            total_boxes += num_of_m_sized_boxes;
        }

        // 更新 n 和 m，进入下一个子问题 (m, r)
        long long remainder = n % m;
        n = m;
        m = remainder;
    }

    // 输出总盒子数
    std::cout << total_boxes << std::endl;

    // 按顺序输出每个盒子的大小，实现字典序最大
    for (const auto& group : box_groups) {
        long long size = group.first;
        long long count = group.second;
        for (long long i = 0; i < count; ++i) {
            std::cout << size << " ";
        }
    }
    std::cout << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot (\log(\min(N, M)) + K))$
- $T$ 是测试用例的数量。
- 算法的核心是欧几里得算法，其迭代次数是 $O(\log(\min(N, M)))$ 。
- $K$ 是输出的盒子总数。在最坏情况下， $K$ 可能会很大（例如 $N=10^9, M=1$ 时， $K \approx 10^9$ ），所以输出本身是复杂度的主要部分。我们每一步生成的盒子数量是 $k \times m$ ，所有这些数量加起来就是总盒子数 $K$ 。因此，总的计算和输出时间和 $K$ 相关。
空间复杂度: $O(\log(\min(N, M)))$
- 我们使用了一个 vector<pair> 来存储不同尺寸的盒子和它们的数量。欧几里得算法的迭代次数是对数级别的，所以这个 vector 的大小也是对数级别的，占用的空间非常小，喵~

知识点总结

这道题真是一次有趣的冒险，对吧！我们来总结一下探险中学到的宝藏知识：

问题转化：最重要的一步是把一个看似复杂的组合划分问题，通过联想和类比，转化为了一个经典的数论模型——欧几里得算法。在算法竞赛中，这种洞察力非常宝贵！
欧几里得算法的应用：我们不仅用到了它的计算过程，更深刻地理解了它每一步 $n = k \cdot m + r$ 分解的物理意义和构造能力。
构造性证明：我们通过归纳法，一步步证明了我们基于欧几里得算法构造出的解是正确的。这种构造性的思维方式是解决许多算法题的关键。
贪心思想：为了实现字典序最大，我们总是优先使用当前允许的最大尺寸的盒子，这是一种贪心策略，并且它恰好能引导我们找到正确的解。

希望我的讲解对你有帮助哦！如果还有不明白的地方，随时可以再来问我，喵~ 💖

MaskAllocation - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​