Codeforces Round 256 (Div. 2) - D. Multiplication Table

Solost

2023 年 04 月 06 日

214 次浏览

暂无评论

1392字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F06%2Fimage.png)

## 题目链接

[题目链接](https://codeforces.com/problemset/problem/448/D)

## 题目大意

给你一个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个是多少即可

~~~cpp
#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;
}
~~~

最后修改：2023 年 04 月 06 日