AcWing 4080. 第k个数
原题链接
中等
作者:
不幸到吃土
,
2024-04-17 01:18:03
,
所有人可见
,
阅读 3
//本题思想:二分
/*
设第k个数为n,另设在n之前的整数个数为res
对于n的左半部的数:res < k 对于n的右半部的数:res >= k
由此二分
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
LL n,m; //若开int,需改为: (1) min((LL)m,mid/i) (2) r = (LL)n*m;
LL k;
bool check(LL mid){
LL res = 0;
for(int i=1;i<=n;i++){ //n行m列
res += min(m,mid/i); //逐行计算满足二分条件的个数:要么整行都满足,要么取[mid/i]
}
return res >= k;
}
int main(){
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;
}
}
printf("%lld",r);
return 0;
}
找不到打卡的地方,就改为题解吧