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;
}
本人蒟蒻,若有错误或不当的地方,还望指正,感谢观看我的博客
标签:二分,www,https,ll,mid,Easy,Problem,lld From: https://www.cnblogs.com/expect-999/p/17609560.html