zcmu 1540第k大数

1540: 第k大数
Time Limit: 10 Sec  Memory Limit: 128 MB
[Submit][Status][Web Board]
Description
有两个序列a,b,它们的长度分别为n和m,那么将两个序列中的元素对应相乘后得到的n*m个元素从大到小排列后的第k个元素是什么?

Input
输入的第一行为一个正整数T (T<=10),代表一共有T组测试数据。

每组测试数据的第一行有三个正整数n,m和k(1<=n, m<=100000,1<=k<=n*m),分别代表a序列的长度,b序列的长度,以及所求元素的下标。第二行为n个正整数代表序列a。第三行为m个正整数代表序列b。序列中所有元素的大小满足[1,100000]。

Output
对于每组测试数据,输出一行包含一个整数代表第k大的元素是多少。

Sample Input
3
3 2 3
1 2 3
1 2
2 2 1
1 1
1 1
2 2 4
1 1
1 1
Sample Output
3
1
1

显然这道题要先对a,b数组排序,这是一定的。 然后,l=a[0]*b[0],r=a[n-1]*b[m-1]开始去查找mid是第几大的数 除了二分之外,这里就算第几大的数这个思路直接关系到会不会TLE.在寻找是第几大数的时候.具体的见代码的注释部分. 还有要说明的时候就是在二分的时候要注意不能当mid满足条件的时候就直接返回结果,这个时候的mid可能在第k+1大个数以及第k大的数之间.
#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,m,k;
long long a[100000];
long long b[100000];

// o(m+n)的思路一个数在由a,b两两相乘得到序列c中属于第几大的数 long long judge(long long mid) { int sum=0; int j=0; for(int i=n-1;i>=0;i--) // 从最大的i开始枚举,因为a,b都是有序的当i情况枚举完之后,后续成立的枚举情况一定在i-1中 for (;j<m;j++) // 当a[i+1][j]满足不了的时候,a[i][j]也是一定满足不了的, 这里就不用重复枚举了,按照前一轮记录的结果来就行了 if(a[i]*b[j]>=mid) { sum+=m-j;// 当j满足的时候,后续的结果也是一定满足的 break; } return sum; } int main() { int pp;scanf("%d",&pp); while(pp--) { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n); for(int i=0;i<m;i++)scanf("%d",&b[i]);sort(b,b+m); long long l=a[0]*b[0]; long long r=a[n-1]*b[m-1]; long long ans; while(l<=r) { long long mid=(r+l)/2; int sum=judge(mid); if(sum>=k) ans=mid,l=mid+1; else r=mid-1; } printf("%lld\n",ans); out:; } return 0; }

 

上一篇:【2020HBU天梯赛训练】7-33 抢红包


下一篇:一文看懂 HashMap 中的红黑树实现原理