题解 | #小红的矩阵#

题目链接

小红的矩阵

题目描述

给定一个 $N \times M$ 大小的矩阵，矩阵第 $i$ 行第 $j$ 列的元素为 $A_{i,j} = i \cdot j$ 。小红想知道矩阵中第 $k$ 小的元素是多少。

解题思路

这是一个在概念矩阵（Conceptual Matrix）中寻找第 $k$ 小元素的问题。

1. 暴力解法的局限性

由于 $N$ 和 $M$ 的范围可达 $10^5$ ，矩阵的大小可能达到 $10^5 \times 10^5 = 10^{10}$ 。直接构建这个矩阵并排序是不可行的，会超出时间和内存的限制。

2. 二分答案

这类“寻找第 $k$ 小/大”的问题，通常是二分答案的经典应用场景。我们可以不直接寻找这个数本身，而是去猜测这个数可能是多少。

单调性：假设我们猜测答案是 $x$ 。我们可以设计一个函数 count_le(x)，用来计算矩阵中有多少个元素小于或等于 $x$ 。这个 count_le(x) 函数显然具有单调非递减的性质：随着 $x$ 的增大，小于等于 $x$ 的元素个数只会增加或不变。

我们的目标是找到一个最小的 $x$ ，使得 count_le(x) 的值大于或等于 $k$ 。这个 $x$ 就是第 $k$ 小的元素。
check(x) 函数的设计：二分答案的核心在于高效地实现 check 函数，即 count_le(x)。我们需要计算满足 $i \cdot j \le x$ 的数对 $(i, j)$ 的数量，其中 $1 \le i \le N$ 且 $1 \le j \le M$ 。

我们可以遍历每一行 $i$ （从 $1$ 到 $N$ ）：
- 对于固定的第 $i$ 行，我们要找的是有多少个 $j$ 满足 $i \cdot j \le x$ ，即 $j \le x / i$ 。
- 同时， $j$ 的取值范围是 $[1, M]$ 。
- 因此，对于第 $i$ 行，满足条件的 $j$ 的个数为 $\min(M, \lfloor x / i \rfloor)$ 。
我们将每一行的这个计数值累加起来，就得到了整个矩阵中不大于 $x$ 的元素总数： $\text{count\_le}(x) = \sum_{i=1}^{N} \min(M, \lfloor x/i \rfloor)$

这个 check 函数的时间复杂度为 $O(N)$ 。
二分过程：
- 我们可以在值域 $[1, N \cdot M]$ 内对答案进行二分查找。
- 取中点 $mid$ 。如果 check(mid) 计算出的计数值小于 $k$ ，说明 $mid$ 太小了，第 $k$ 小的数一定比 $mid$ 大，所以我们去右半区间 $[left+1, right]$ 查找。
- 如果计数值大于或等于 $k$ ，说明 $mid$ 可能就是答案，或者答案更小，所以我们去左半区间 $[left, mid-1]$ 查找。

代码

c++
java
python

#include <iostream>
#include <algorithm>

using namespace std;

// 计算矩阵中有多少个元素小于等于 x
long long count_le(long long x, long long n, long long m) {
    long long count = 0;
    for (long long i = 1; i <= n; ++i) {
        count += min(m, x / i);
    }
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, m, k;
    cin >> n >> m >> k;

    long long left = 1, right = n * m;
    long long ans = n * m;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (count_le(mid, n, m) >= k) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    // 计算矩阵中有多少个元素小于等于 x
    private static long countLe(long x, long n, long m) {
        long count = 0;
        for (long i = 1; i <= n; i++) {
            count += Math.min(m, x / i);
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        long k = sc.nextLong();

        long left = 1, right = n * m;
        long ans = n * m;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (countLe(mid, n, m) >= k) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }
}

def count_le(x, n, m):
    """计算矩阵中有多少个元素小于等于 x"""
    count = 0
    for i in range(1, n + 1):
        count += min(m, x // i)
    return count

def main():
    n, m, k = map(int, input().split())

    left, right = 1, n * m
    ans = n * m

    while left <= right:
        mid = (left + right) // 2
        if count_le(mid, n, m) >= k:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
            
    print(ans)

if __name__ == "__main__":
    main()

算法及复杂度

算法：二分答案。
时间复杂度： $O(N \log(NM))$ 。二分查找的值域范围是 $[1, NM]$ ，需要 $O(\log(NM))$ 次迭代。在每次迭代中，check 函数需要 $O(N)$ 的时间来遍历每一行并计算计数值。
空间复杂度： $O(1)$ 。我们没有存储整个矩阵，只需要常数级别的额外空间。