题目链接

题目链接

题目大意

给你一个n,m问你n*m中第k大的数是多少

题解

刚开始想着如何数出来是第几个，然后虽然想暴力但是压根存不了，5e5*5e5太大了，看了题解后二分，二分这个答案，我们查的数是第几个。

如果当前数是x,那么我们推算他比小的数的个数，根据乘法表的性质，是1*1,1*2,1*3.....第一个数是行号，第二个数是列，假设现在这个乘法表是5 * 5，那么11这个数的位置就是第一行:min(11/i,m) = 5,因为列号正好就是这一行的第几个，所以x除当前数就是第几个数，但是不能比列的数目还多，第二行:min(11/2,m) = 5, 第三行:min(11/3,m) = 3,所以他的位置就是5+5+3=13暴力枚举每个数的位置，然后算出来第k个是多少即可

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

ll n, m, k;

bool check(ll x){
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        sum += min(x / i, m);
    }
    return sum >= k;
}

void solve()
{
    cin >> n >> m >> k;
    ll l = 1, r = n * m;
    while(l < r){
        ll mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}