题目大意:
有一个$n*m$的矩阵,满足第$i$行第$j$列的元素值为$i*j$,求第$k$大的值。
数据范围:$n,m leq 500000$
思路:
考虑二分答案。
假设我们现在枚举出了一个值为$x$。
我们考虑到每一行比这个$x$小的个数,要么是$m$(当前行最大的数为$i*m$),要么是$x/i$。
直接统计答案即可。
复杂度:$O(nlogn)$。
代码:
#include <bits/stdc++.h> typedef long long ll; const ll lim = 250000000000; using namespace std; ll n, m, k, ans; bool check(ll x) { ll res = 0; for(ll i = 1; i <= n; i++) res += min((x - 1) / i, m); return res < k; } int main() { cin >> n >> m >> k; ll l = 0, r = lim; while(l <= r) { ll mid = (l + r) >> 1; if(check(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } cout << ans << endl; return 0; }