二分
分析
如果第k个数是x,意味着小于等于x-1(x-2、x-3、…)的数的个数必然小于k个,大于等于x(x+1、x+2、…)的数的个数必然大于等于k个。
思路
通过以上分析可以看出数x是条件$ \geq k $ 的数的最小值
,而二分算法就是求满足某一性质的分界点。故此题用二分求解。
至于小于x的数如何统计?
矩阵每一行都是严格单调递增的,那么遍历遍历每行,累加x*i<mid
的数即可
#include <iostream>
using namespace std;
typedef long long LL;
LL n, m, k;
// 小于mid的个数
bool check(LL mid)
{
LL res = 0;
for (int i = 1; i <= n; i ++ ) // i从1开始枚举
res += min(m, mid / i); // 累加每行小于mid的数的个数
return res < k;
}
int main()
{
cin >> n >> m >> k;
LL l = 1, r = n * m;
while(l < r)
{
LL mid = l + r >> 1;
if (check(mid)) l = mid + 1;
else r = mid;
}
cout << r << endl;
return 0;
}