本文共 1257 字，大约阅读时间需要 4 分钟。

【题解】

n*m有1e10显然我们不可能直接对生成的序列做什么操作，所以我们考虑通过原始序列作出某种判断得出答案。

询问的n*m个元素从大到小排序，这样的一个数组显然是具有单调性的，所以很容易想到用二分。

但是想到怎么二分并且优化时间复杂度就不是特别容易了，要一点思维。

我们知道，这个数组的最大值一定是a[0]*b[0]，最小值一定是a[n-1]*b[m-1]，所以我们可以先对两个数组进行排序，然后根据这个边界值定下L和R开始做二分，每次判断Mid是否是整个数组的第k大元素，所以我们在当Mid是第>=k大元素的时候，我们就可以考虑更大的元素，令L=Mid+1，更新答案；否则令R=Mid-1. 

在判断Mid是否是整个数组的第k大元素的时候，我们需要注意到，如果我们从序列a的最大值和b的最小值开始逐个判断，如果此时a[i]*b[j]<Mid，那么下一个可能>=Mid的数字只会出现在a[i]*b[j+1]，因为a[i]是逐渐变小的b[j]是逐渐变大的。因此我们可以把复杂度从O(n*m)优化到O(n+m)，而二分的复杂度为O(logn)。

时间复杂度为O(nlogn)。

【代码】

#include 
   
    using namespace std;typedef long long ll;const int N=1e5+5;int n,m;ll k;ll a[N],b[N];bool check(ll x){    ll sum=0;    int j=0;    for(int i=n-1;i>=0;i--)        for(;j
    
     =x){                sum+=m-j;                break;            }    return sum>=k;}int main(){    int T; scanf("%d",&T);    while(T--){        scanf("%d%d%lld",&n,&m,&k);        for(int i=0;i
    
   

【题目】

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

转载地址：http://xhfen.baihongyu.com/