526互联

An Easy Problem（二分）

发布时间 2023-08-06 16:54:20作者: 只会做红色题

GDCPC A题

原题链接：https://cpc.csgrandeur.cn/csgoj/problemset/problem?pid=1168

类似的题目及视频解释链接：
题目：https://www.acwing.com/problem/content/description/4083/

相关视频讲解https://www.acwing.com/video/3568/

本题可以转化成二维数组，每一行数都是呈现递增的，所以可以使用二分找出序列最大为第k的项
题解代码如下

#include<iostream>
#include <algorithm>

using namespace std;
typedef  long long ll;
ll n, m, k;

bool check(ll x)
{
    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += min(m, x / i); //找出每一行i中有多少数小于mid并累加，注意一个二维数组一行中最大有m个数,x/i可能超出m,所以为了防止溢出，取较小值。
    }
    return res >= k;
}
int main()
{
    scanf_s("%lld %lld %lld", &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;
    }
    printf("%lld", l);
    return 0;
}

本人蒟蒻，若有错误或不当的地方，还望指正，感谢观看我的博客