【算法刷题】蓝桥杯：肖恩的乘法表（二分答案 + 矩阵单调性）

📌 题目链接与描述

• 题目名称：肖恩的乘法表
• 数据规模：$1\le n,m\le 5\times 10^5$， $1\le k\le n\times m$
• 核心问题：给定一个 $n\times m$ 的乘法表，求其中所有元素从小到大排序后的第 $k$ 小数字。

❌ 常见坑点与踩坑记录

1. 暴力思路：内存与时间双双超限（MLE & TLE）

• 错误做法：用 vector 存储所有 $n\times m$ 个乘法表数字，排序后输出 a[k-1]。
• 原因分析：$n\times m\le 2.5\times 10^{11}$，占用上百 GB 内存，严重超出 256MB 限制；排序时间复杂度为 $\mathcal{O}(nm\log (nm))$，远超 2 秒限制。

2. 数据类型溢出（WA 的元凶！）

• 错误写法：int n, m; long long r = n * m;
• 原因分析：虽然变量 r 是 long long，但由于 n 和 m 是 int，二者相乘的中间过程依然以 32 位 int 进行计算，结果会发生整型溢出变成负数，导致二分右边界错乱！
• 正确做法：n, m, k 必须直接声明为 long long！

💡 解题核心思路：二分答案（Binary Search）

由于乘法表具有单调性（数字越大，乘法表中“小于等于该数字”的数量就越多），我们可以将求“第 $k$ 小的数”转化为在范围 $[1,n\times m]$ 内二分查找数值 mid。

关键点：如何快速计算 check(mid)？

在乘法表第 $i$ 行中，数值依次为 $i\times 1,i\times 2,\dots ,i\times m$：

• 满足 $i\times j\le \text{mid}$ 的列数 $j$ 满足 $j\le \lfloor \text{mid}/i\rfloor$。
• 考虑到每一行最多只有 $m$ 列，因此第 $i$ 行小于等于 mid 的元素个数为：$\min (m,\lfloor \text{mid}/i\rfloor )$。
• 遍历 $1\sim n$ 行求和，可以在 $\mathcal{O}(n)$ 的时间复杂度内算清整张表中 $\le \text{mid}$ 的总个数！

💻 最终 AC 代码 (C++)

#include <iostream>
#include <algorithm>

using namespace std;

// 校验乘法表中 <= mid 的元素个数是否 >= k
bool check(long long mid, long long n, long long m, long long k) {
    long long count = 0;
    for (long long i = 1; i <= n; i++) {
        count += min(m, mid / i); // 计算第 i 行 <= mid 的元素个数
    }
    return count >= k;
}

int main() {
    // 快速 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    long long l = 1;
    long long r = n * m; // 注意：必须用 long long 避免溢出
    long long res = 0;

    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid, n, m, k)) {
            res = mid;     // mid 满足条件，记录答案
            r = mid - 1;   // 尝试寻找更小的可行解
        } else {
            l = mid + 1;   // mid 太小，向右扩大范围
        }
    }

    cout << res << "\n";

    return 0;
}

⏱️ 复杂度分析

• 时间复杂度：$\mathcal{O}(n\log (n\cdot m))$
  • 二分查找次数：${\log }_2(2.5\times 10^{11})\approx 38$ 次。
  • 单次检查：每次 check 仅需 $n=5\times 10^5$ 次循环。
  • 总体评估：整体计算量大约为 $1.9\times 10^7$ 次，实际耗时在 30ms 左右，轻松通过。
• 空间复杂度：$\mathcal{O}(1)$，仅使用常数级变量空间。

📝 刷题总结

1. 场景总结：遇到“求第 $k$ 大/小”、“最大值的最小值”且数据范围极其庞大无法直接排序/存储时，优先思考二分答案。
2. 细节把控：涉及 $10^9$ 以上级别乘法运算时，从源头将所有输入变量定义为 long long，防止隐式溢出。