题解 | 小红的矩阵

/*
我的主要思路是第k小的元素是使得小于自身的数为k-1个成立,小于等于自身的数大于等于k个成立的最小的元素
接下来要实现的是check(x)函数检测矩阵中有多少个小于等于x的元素，这个利用此矩阵的特殊性可以在O(n)内实现
之后在矩阵的元素中随x递增,check(x)的函数值也是递增的，这就表明可以用二分查找法去找寻check(x)>=k成立的x的值。

1、但是有个问题就是取到的0到m * n之间的某个数并不一定会在矩阵中出现，这个该怎么办？如何解决？
针对1，假设有一个数m不在矩阵内但是小于等于它的数有k个，那么找到这k个数中的最大的数，小于等于它的数也有k个这个矩阵中的数比m小但也满足条件，所以说假设不成立，不用担心那种情况
*/



#include <stdio.h>

//check(x)函数检测矩阵中有多少个小于x的元素,n,m表示确定大小的符合要求的矩阵，x表示要查取的数的值
long long check(long long n, long long m, long long x){
    //对于确定的第i行，要使得i * j <= x，必须要使得j <=[x / i],此行应该有min{m,[x / i]}个数满足条件
    long long num = 0;
    //循环，累加每一行的满足条件的数得到结果
    for(long long i = 1; i <= n; i ++){
        long long tmp = x / i;
        long long num_i = m < tmp ? m : tmp;
        num += num_i;
    }
    return num;
}

int main() {
    //读取值
    long long n, m, k;
    scanf("%lld %lld %lld\n",&n, &m, &k);

    //二分查找,res保留结果
    long long l = 1;
    long long h = n * m;
    long long res = -1;
    while(l <= h){
        long long mid = l + (h - l) / 2;
        if(check(n, m, mid) >= k){
            res = mid;
            h = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    printf("%lld\n", res);
    return 0;
}