4080. 第k个数

原题链接
给定一个 n×m 的方格矩阵，每个方格内都有一个整数元素。
其中第 i 行第 j 列的方格中的元素为 i×j（行和列都从 1 开始编号）。
现在，需要你将这 n×m 个整数按照非严格单调递增的顺序一一写出。

请问，你写出的第 k 个整数是多少。

输入格式：
一行，三个整数 n,m,k 。

输出格式：
一行，输出你写出的第 k 个整数。

数据范围
前 6 个测试点满足 1 ≤ n, m ≤ 10。
所有测试点满足 1 ≤ n, m ≤ 5 × 10e5，1 ≤ k ≤ n × m。

输入样例1：
2 2 2
输出样例1：
2

输入样例2：
2 3 4
输出样例2：
3

输入样例3：
1 10 5
输出样例3：
5

思路：

#include<bits/stdc++.h>
using namespace std;

//非严格单调递增是指允许有重复数据出现的递增序列

/**
 * 数据范围：
 * 1 ≤ n , m ≤ 5 * 10e5，
 * 1 ≤ k ≤ n * m
 * 所以 1 <= k <= 2.5 * 10e11  ==>>   考虑long long int 型整数
 **/
typedef long long int LL; 


LL n, m, k;  //n:行数；m:列数；k:询问位置

//条件判断函数
bool check(LL midnum)
{
/**用于统计<=midnum的个数，
 * 当<=midnum的个数>=k，则满足条件，返回true
 * 当<=midnum的个数<k，则满足条件， 返回false
* */

    LL ans = 0;  //计数变量

    for(LL i = 1; i <= n; i++) //从第1行开始枚举
    {
        ans += min((midnum / i), m);  //累加每行小于midnum的个数
    }

    if(ans >= k) return 1;  //此时答案为mid或者在mid的左区间->满足条件

    else return 0;
}

int main()
{
    scanf("%lld%lld%lld", &n, &m, &k);

    LL l = 1, r = n * m;  //左右指针

    //当满足条件时，搜索区间向左缩减，即[l,r] --> [l,mid]
    //每一次遍历更新，mid逐渐的向第k个位置靠近，直到l == r为止
    while(l < r)
    {
        LL mid = l + r >> 1;

        //条件：寻找条件>=k的最小值，即当条件>=k时，均满足条件
        if(check(mid))
            r = mid;
        else
            l = mid + 1;  //此时mid左区间的数（包括mid本身）都不满足个数>=k的条件，所以更新l时需要mid+1
    }

    printf("%lld", r);  //也可以输出l，此时r和l指针指向了==k的位置

    return 0;
}