题解：n×m 矩阵第 k 小元素

题目分析

问题描述

给定 n×m 大小的矩阵，其中第 i 行第 j 列的元素为 i×j（1≤i≤n，1≤j≤m），要求找出矩阵中第 k 小的元素。

分析题干

• 矩阵规模极大（n,m≤1e5），直接生成矩阵会占用 O (nm) 空间，完全超出内存限制；
• 暴力排序所有元素更是不可能（元素总数达 1e10，时间复杂度无法承受）；
• 矩阵元素并非有序排列，但每行 / 每列具有单调性，可利用二分查找优化。
• 矩阵元素最小值为 1（1×1），最大值为 n×m（n×m），所有元素都在 [1, n×m] 区间内；
• 对于任意一个数 x，能快速统计矩阵中 ≤x 的元素个数：第 i 行的元素是 i×1, i×2, ..., i×m，均为 i 的倍数；该行中 ≤x 的元素个数为 min (x/i, m)（x/i 是不大于 x 的 i 的倍数个数，m 是每行最大元素数，防止超出列数）；
• 第 k 小的元素 x₀ 满足：矩阵中 ≤x₀ 的元素个数 ≥k，且 ≤x₀-1 的元素个数 <k，这正是二分查找的判定条件。

ACnode

#include <bits/stdc++.h>
using namespace std;
#define int long long  // 定义int为long long，避免1e5×1e5=1e10溢出

int n, m, k;  // 全局变量存储n、m和目标第k小

int work(int x) {
    int res = 0;  // 结果计数器
    for (int i = 1; i <= n; i++) {  // 遍历每一行
        // 每行≤x的元素个数：x/i（i的倍数中≤x的个数）和m（列数上限）取最小值
        res += min(x / i, m);
        // 提前终止：当x/i=0时，后续行i更大，x/i仍为0，无需继续遍历
        if (x / i == 0) {
            break;
        }
    }
    return res;
}

signed main() { 
    cin >> n >> m >> k;  
    int l = 1, r = n * m;  // 二分查找的区间：[最小值1，最大值n×m]
    int ans = 0;  // 存储最终答案

    // 开始二分查找
    while (l <= r) {
        // 计算中间值mid，用位运算>>1代替/2，避免溢出（等价于(l+r)/2）
        int mid = l + ((r - l) >> 1);
        // 统计≤mid的元素个数：若≥k，说明mid是候选答案，尝试更小的数
        if (work(mid) >= k) {
            ans = mid;  // 记录当前候选答案
            r = mid - 1;  // 向左缩小查找区间
        } else {
            // 若≤mid的元素个数<k，说明答案在更大的区间，向右缩小
            l = mid + 1;
        }
    }

    cout << ans << endl;  // 输出第k小的元素
    return 0;
}

复杂度分析

• 时间复杂度：O(n log(nm))二分查找次数：log (nm)，由于 nm≤1e10，log2 (1e10)≈34，次数极少；每次二分的统计操作：O (n)，但通过 x/i=0 提前终止，实际遍历次数远小于 n；
• 空间复杂度：O (1)，仅使用常数个变量，无额外空间开销。