Kth Largest

Kth Largest

Totalsubmit: 970   Accepted: 168  

Description

There are two sequences A and B with N (1<=N<=10000) elements each. All of the elements are positive integers. Given C=A*B, where '*' representing Cartesian product, c = a*b, where c belonging to C, a belonging to A and b belonging to B. Your job is to find the K'th largest element in C, where K begins with 1.

Input

Input file contains multiple test cases. The first line is the number of test cases. There are three lines in each test case. The first line of each case contains two integers N and K, then the second line represents elements in A and the following line represents elements in B. All integers are positive and no more than 10000. K may be more than 10000.

Output

For each case output the K'th largest number.

Sample Input

2

2 1

3 4

5 6

2 3

2 1

4 8

Sample Output

24

8

Submit

二分套二分，詳細思路見注釋

/*

思路：

left=a[0]*b[0];

right=a[n-1]*b[n-1];

mid=(left+right)/2;

while(left<=right)

{

if(solve(mid))

right=mid-1;

else

left=mid+1;

}

bool solve(mid)//判斷<=mid的個數是否比m（要求值）大

{

t=how many numbers smaller than mid;

//how to calculate t:

for(i=0;i<n-1;i++)

{

int l=0;

int r=n-1;

while(l<=r)

{

int mm=(l+r)/2;

if(a[i]*b[mm]>mid)

r=mm-1;

else

l=mm+1;

}

t+=l;

if(t>m)

break;

}

m=need m numbers smaller than mid;

if(t<m)//mid 小了

return false;

else//mid 大了

return true;

}*/

#include <iostream>

#include <cstdio>

using namespace std;

const int N = 10005;

int A[N], B[N];

int main(void)

{

int n, m, cas;

scanf("%d", &cas);

while (cas--)

{

scanf("%d%d", &n, &m);

for (int i = 0; i < n; ++i)

scanf("%d", A + i);

for (int i = 0; i < n; ++i)

scanf("%d", B + i);

sort(A, A + n);

sort(B, B + n);

int l = A[0] * B[0], r = A[n - 1] * B[n - 1];

m = n * n - m + 1;

while (l <= r)

{

int mid = (l + r) >> 1; //num_k

int lt = 0;

for (int i = 0; i < n; ++i)

{

int a = 0, b = n - 1;

while (a <= b)

{

int c = (a + b) >> 1;

int t = A[i] * B[c];

if (t > mid)//mid is num_k

b = c - 1;

else a = c + 1;

}

lt += a;

if (lt > m)

break;

}

if (lt >= m)//lt or m represents how many numbers smaller than m

r = mid - 1;

else l = mid + 1;

}

printf("%d/n", l);

}

return 0;

}