题目链接

小红的矩阵

题目描述

给定一个 大小的矩阵，矩阵第 行第 列的元素为 （ 从 1 开始）。小红想知道矩阵中第 小的元素是多少。

解题思路

这是一个在隐式、有序的矩阵中寻找第 小元素（k-th order statistic）的经典问题。由于 和 的范围很大，我们无法实际构建出整个矩阵。这个问题的关键在于矩阵的单调性，这使得我们可以对答案进行二分查找。

1. 二分查找答案

我们可以二分查找最终的答案，设答案为 ans。答案的取值范围显然在 之间。

对于二分查找中的每一个猜测值 x，我们需要能够高效地回答一个问题：“矩阵中有多少个元素小于或等于 x？”。我们把这个计数函数称为 count_le(x)。

二分查找的逻辑如下：

  • 设查找范围为 [low, high]。
  • 取中间值 mid，计算 count = count_le(mid)。
  • 如果 count >= k：这说明小于等于 mid 的数至少有 k 个。那么，真正的第 小的数可能就是 mid，或者是一个比 mid 更小的数。因此，我们将 mid 作为一个潜在的答案，并尝试在更小的范围内搜索，即 high = mid - 1。
  • 如果 count < k：这说明小于等于 mid 的数不足 k 个。那么，第 小的数一定比 mid 大。因此，我们必须在更大的范围内搜索，即 low = mid + 1。

通过这种方式，我们最终找到的 ans 将是满足 count_le(ans) >= k 的最小值，这正是我们要求的第 小的元素。

2. 高效实现 count_le(x)

count_le(x) 函数的实现是本题的核心。我们需要计算满足 的数对 的数量（其中 ）。

我们可以遍历每一行，从 到 ：

  • 对于固定的第 行，我们要找有多少个 满足 。
  • 这个不等式可以变形为 。
  • 同时， 还必须满足 。
  • 因此，在第 行，满足条件的 的数量为 。

我们将每一行的这个计数值累加起来，就得到了 count_le(x) 的结果。这个计算过程的时间复杂度是 。

3. 整体复杂度

  • 时间复杂度: 。二分查找需要大约 次迭代，每次迭代内部的 count_le 函数需要 的时间。
  • 空间复杂度: 。

代码

#include <iostream>
#include <algorithm>

using namespace std;

// Function to count numbers less than or equal to x in the matrix
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 low = 1, high = n * m;
    long long ans = -1;

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

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    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 low = 1;
        long high = n * m;
        long ans = -1;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (countLe(mid, n, m) >= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        System.out.println(ans);
    }

    // Function to count numbers less than or equal to x in the matrix
    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;
    }
}

import sys

def solve():
    try:
        n, m, k = map(int, sys.stdin.readline().split())
    except (IOError, ValueError):
        return

    def count_le(x, n, m):
        count = 0
        for i in range(1, n + 1):
            count += min(m, x // i)
        return count

    low, high = 1, n * m
    ans = -1

    while low <= high:
        mid = low + (high - low) // 2
        if mid == 0: # Avoid division by zero if low is 0, though not possible with 1-based low
            low = 1
            continue
            
        if count_le(mid, n, m) >= k:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

solve()

算法及复杂度

  • 算法：二分查找答案

  • 时间复杂度：。

    • 二分查找的答案范围是 ，因此查找次数为 。
    • 在每次二分检查中，count_le 函数需要遍历 行来计算，时间复杂度为 。
    • 总时间复杂度为两者相乘。

  • 空间复杂度：。

    • 除了存储输入的几个变量外，算法不需要与 大小成正比的额外空间。