We have two arrays of integer with n elements ( n <= 10^5 ) , consider:
a1 a2 a3 ... an
b1 b2 b3 ... bn
( abs(a[i],b[i]) <= 10^9 )
print maximum first k element c=(a[i] * b[j]) ( 1<=i,j<=n)
For example: input: n=3 k=3
a={1,2,3}
b={4,5,6}
Correct output: 6 12 18
I'm trying to solve problem like this , but i don't have any idea for getting "AC" , so i need some helps , thank everybody.
We will use binary search on the answer. Let’s say that we want to check if some number x is greater or less than kth pair a[i] * b[i]. We can easily count how many pairs are greater: a[i] * b[i] > x => a[i] > x / b[i]. So, for every i we can find how many a[j] are greater than x / b[i] using two pointers or binary search in a sorted a. If this number is less than k, we know that x must be greater, otherwise it must be less. After we found a kth value, it’s easy to recover the final array.
OMG thank you!
Auto comment: topic has been updated by Tboros_kylie (previous revision, new revision, compare).