小红的矩阵

[题目链接](https://www.nowcoder.com/practice/c77b7301464f4cfcacc9492a3c999f65)

思路

给一个 $n \times m$ 的矩阵，第 $i$ 行第 $j$ 列的元素为 $i \times j$ ，求矩阵中第 $k$ 小的元素。

暴力行不通

如果 $n, m$ 很大，我们没法真的把所有 $n \times m$ 个元素排序——那可能有 $10^{18}$ 个数。

二分答案

换个角度想：如果我们猜一个值 $x$ ，能不能快速算出矩阵里有多少个元素 $\leq x$ ？

对于第 $i$ 行，元素分别是 $i, 2i, 3i, \ldots, mi$ 。其中 $\leq x$ 的有 $\min(\lfloor x / i \rfloor, m)$ 个。把所有行加起来就得到总个数：

$ $\text{count}(x) = \sum_{i=1}^{n} \min\!\left(\left\lfloor \frac{x}{i} \right\rfloor,\, m\right)$ $

这个求和只需要 $O(n)$ 时间。

二分框架

如果 $\text{count}(x) \geq k$ ，说明答案 $\leq x$ ，缩小右边界。
如果 $\text{count}(x) < k$ ，说明答案 $> x$ ，抬高左边界。

二分范围 $[1, n \times m]$ ，总复杂度 $O(n \log(nm))$ 。

样例演示

$n = 3, m = 3, k = 4$ ，矩阵为：

\begin{bmatrix}

1 & 2 & 3 \\

2 & 4 & 6 \\

3 & 6 & 9

\end{bmatrix}

排序后为 $1, 2, 2, 3, 3, 4, 6, 6, 9$ ，第 4 小是 $3$ 。

二分到 $x = 3$ 时：第 1 行有 $\min(3, 3) = 3$ 个，第 2 行有 $\min(1, 3) = 1$ 个，第 3 行有 $\min(1, 3) = 1$ 个，总共 $5 \geq 4$ ，所以答案不超过 $3$ 。而 $x = 2$ 时总共 $3 < 4$ ，所以答案就是 $3$ 。

复杂度

时间复杂度： $O(n \log(nm))$
空间复杂度： $O(1)$

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, m, k;
    scanf("%lld%lld%lld", &n, &m, &k);
    long long lo = 1, hi = n * m;
    while(lo < hi){
        long long mid = lo + (hi - lo) / 2;
        long long cnt = 0;
        for(long long i = 1; i <= n; i++)
            cnt += min(mid / i, m);
        if(cnt >= k) hi = mid;
        else lo = mid + 1;
    }
    printf("%lld\n", lo);
    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(), m = sc.nextLong(), k = sc.nextLong();
        long lo = 1, hi = n * m;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            long cnt = 0;
            for (long i = 1; i <= n; i++)
                cnt += Math.min(mid / i, m);
            if (cnt >= k) hi = mid;
            else lo = mid + 1;
        }
        System.out.println(lo);
    }
}