第K大的数 题解

第K大的数 题解

文章目录

• • • • 题面
  • 解析
  • • • 提示

题面

题目描述
数组A和数组B，里面都有n个整数。
数组C共有n^2个整数，分别是：
A [ 0 ] × B [ 0 ] , A [ 0 ] × B [ 1 ] … A [ 0 ] × B [ n − 1 ] A[0] times B[0],A[0] times B[1] dots A[0] times B[n-1] A[0]×B[0],A[0]×B[1]…A[0]×B[n−1]
A [ 1 ] × B [ 0 ] , A [ 1 ] × B [ 1 ] … A [ 1 ] × B [ n − 1 ] A[1] times B[0],A[1] times B[1] dots A[1] times B[n-1] A[1]×B[0],A[1]×B[1]…A[1]×B[n−1]
… dots …
A [ n − 1 ] × B [ 0 ] , A [ n − 1 ] × B [ 1 ] … A [ n − 1 ] × B [ n − 1 ] A[n - 1] times B[0],A[n - 1] times B[1]dots A[n - 1] times B[n - 1] A[n−1]×B[0],A[n−1]×B[1]…A[n−1]×B[n−1]
是数组A同数组B的组合,求数组C中第K大的数。
例如：
A ： 1 2 3 , B ： 2 3 4. A：1 2 3,B：2 3 4. A：1 2 3,B：2 3 4.
A A A 与 B B B 组合成的 C C C 为

共 9 9 9个数。
输入
第1行：2个数N和K，中间用空格分隔。N为数组的长度，K对应第K大的数。( 2 ≤ N ≤ 50000 ， 1 ≤ K ≤ 1 0 9 2 le N le 50000，1 le K le 10^9 2≤N≤50000，1≤K≤109 )
第2 - N + 1行：每行2个数，分别是 A [ i ] A[i] A[i] 和 B [ i ] B[i] B[i] 。( 1 ≤ A [ i ] , B [ i ] ≤ 1 0 9 1 le A[i],B[i] le 10^9 1≤A[i],B[i]≤109)
输出
输出第K大的数。
样例输入
3 2
1 2
2 3
3 4
样例输出
9

解析

不难想到暴力做法，枚举所有的结果，时间复杂度 Θ ( N 2 log ⁡ 2 N 2 ) Thetaleft(N^2log_2 N^2right) Θ(N2log2​N2) 空间复杂度 Θ ( N 2 ) Thetaleft(N^2right) Θ(N2) 明显TLE+MLE。
我们发现，答案满足单调性，我们二分答案。
那么 check(x) 就是查找 C C C 中比 x x x 大的数字个数。
然后考虑 check(x) 函数的设计，一个一个枚举也可以，但是，我们发现，对于每个 a k a_k ak​ ，我们又可以进行一次二分查找来找到比 x x x 大的值中最小的一个，然后进行计算得到结果。
代码：

#include<cstdio>
#include<algorithm>
#define maxn 50039
using namespace std;
typedef long long ll;
typedef long long Type;
inline Type read(){Type sum=0;int flag=0;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') c=getchar(),flag=1;while('0'<=c&&c<='9'){sum=(sum<<1)+(sum<<3)+(c^48);c=getchar();}if(flag) return -sum;return sum;
}
ll a[maxn],b[maxn];
int n,k;
int find(ll x){int sum=0;int left,right,middle;for(int i=1;i<=n;i++){left=0,right=n+1;while(left+1<right){middle=(left+right)>>1;if(a[i]*b[middle]>=x) left=middle;else right=middle;}sum+=left;}//printf("%lld %dn",x,sum);return sum;
}
int cmp(ll xx,ll yy){return xx>yy;
}
ll l,r,mid;
int main(){n=read(); k=read();for(int i=1;i<=n;i++){a[i]=read();b[i]=read();}sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);l=0,r=a[1]*b[1]+1;while(l+1<r){mid=(l+r)/2;if(find(mid)>=k) l=mid;else r=mid;}printf("%lld",l);return 0;
}

提示

如果你没有AC，注意一下几点：

1. 除法带来的精度问题
2. 十年OI一场空，不开long long见祖宗