4080. 第k个数
给定一个 $n×m$ 的方格矩阵,每个方格内都有一个整数元素。
其中第 $i$ 行第 $j$ 列的方格中的元素为 $i×j$(行和列都从 $1$ 开始编号)。
现在,需要你将这 $n×m$ 个整数按照非严格单调递增的顺序一一写出。
请问,你写出的第 $k$ 个整数是多少。
输入格式
一行,三个整数 $n,m,k$。
输出格式
一行,输出你写出的第 $k$ 个整数。
数据范围
前 $6$ 个测试点满足 $1≤n,m≤10$。
所有测试点满足 $1≤n,m≤5×10^5$,$1≤k≤n×m$。
输入样例1:
2 2 2
输出样例1:
2
输入样例2:
2 3 4
输出样例2:
3
输入样例3:
1 10 5
输出样例3:
5
解题思路
二分
二分答案,要求判断当前数在所有数中的排名,即:找有多少个数比当前数小,按行枚举,从第一行开始,找出其在第一行中的排名,假设找到该位置,由于该列小于下一行的对应列,所以当前数在下一行的排名只会在前面,即从上往下时当前数的排名只会往前。这样就能在 $O(n+m)$ 的复杂度内找出当前数的排名,接着二分即可~
- 时间复杂度:$O((n+m)\times log(nm))$
代码
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
int n,m;
LL k;
bool ck(LL x)
{
int j=m;
LL s=0;
for(int i=1;i<=n;i++)
{
while(j&&1ll*i*j>x)j--;
s+=j;
}
return s>=k;
}
int main()
{
scanf("%d%d%lld",&n,&m,&k);
LL l=1,r=1ll*n*m,res;
while(l<=r)
{
LL mid=l+r>>1ll;
if(ck(mid))
{
res=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%lld",res);
return 0;
}