两个数列取第k小数

1 1 ．第K K 小数 ( ( number .cpp/c/pas) 【问题描述】 有两个正整数数列，元素个数分别为N和M。从两个数列中分别任取一个数 相乘，这样一共可以得到N*M个数，询问这N*M个数中第K小数是多少。 【输入格式】 输入文件名为number.in。 输入文件包含三行。 第一行为三个正整数N,M和K。 第二行为N个正整数，表示第一个数列。 第三行为M个正整数，表述第二个数列。 【输出格式】 输出文件名为number.out。 输出文件包含一行，一个正整数表示第K小数。 【输入输出样例1 1 】 number.in  number.out 2 3 4 1 2 2 1 3 3 【输入输出样例2 2 】 number.in  number.out 5 5 18 7 2 3 5 8 3 1 3 2 5 16 【数据规模与约定】 样例点编号  N  M  K  元素大小(≤) 1  20  20  150  10^4 2  50  50  2000  10^4 3  100  80  5000  10^9 4  200  200  26000  10^9 5  10000  10000  50050000  10^4 6  1000  20000  9500000  10^4 7  1000  20000  10000500  10^9 8  2000  20000  190000  10^9 9  2000  20000  199000  10^9 10  20000  20000  210005000  10^4 11  20000  20000  210000  10^5 12  20000  20000  200000  10^9 13  20000  20000  220000500  10^5 14  20000  20000  199000500  10^9 15  200000  200000  180000  10^4 16  200000  200000  200000  10^9 17  2000  200000  100001500  10^9 18  200000  180000  19550000000  10^5 19  200000  200000  19900010000  10^9

20  200000  200000  20000010000  10^9

分析：

对于这个问题，如果一个问题取第k小数，类比前面的poj2104，我们可以知道用二分，我们二分结果，然后计算有多少个数比其小。

要注意的是，计算个数也是有技巧的。仅仅是两层循环是不可以的。我们可以先排好序，要知道a[i]*b[j]>=mid那么a[i+1]*b[j]>=mid,具体细节看程序。

参考程序：

#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=210000; LL a[maxn],b[maxn]; int n,m; LL k; int main(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout); scanf("%d%d%lld",&n,&m,&k); for (int i=0;i<n;i++)scanf("%lld",&a[i]); for (int i=0;i<m;i++)scanf("%lld",&b[i]); sort(a,a+n);sort(b,b+m); LL l=0,r=a[n-1]*b[m-1]+1; while (l+1<r){ LL mid=(l+r)>>1; LL sum=0; int p=m-1; for (int i=0;i<n;i++){ while (p>=0 && a[i]*b[p]>=mid)p--; sum+=p+1; } if (sum>=k)r=mid; else l=mid; } printf("%lld",l); return 0; }