I have a problem set I cannot seem to find a solution to...
I gotta array of pair of int vector< pair<int, int > > array;
I have to find a pair where
the value of array[i].first * P + array[i].second * Q is the minimum
the problem is I cannot just loop trough it and find the minimum
because P and Q is input-ed multiple times and it doing a linear serach have a complexity of O(n^2) which is not fast enough
How do I sort the array so that I can binary search it ?
I cannot seem to get an Idea on how should I sort it
Also if you want the extra speed you may want to consider a C array instead of a C++ vector. Without knowing the number of elements it would be hard to be more specific. I would say if you don't plan to use any dynamic allocation, use a C array.
Alternatively, you could just write your own binary search, as it isn't very hard, although the STL offers so many implementations of the concept of binary search that you would be hard pressed to find something that hasn't already been done well.
hey hey there, I am asking on how should I sort it...
to make it more specific, what is the compare function ???
I know how to sort a the pair based on their first and second into order by using <algorithm> STL or even manually but sort them like that but does that help me solve the problem
P and Q are input-ed multiple times
you can say that P and Q are arrays
but I don't keep them in array I just take P and Q then output the result right away
Calculating them one by one and search for the minimum would be an linear search, wouldn't it ?
I am trying to find a more optimal solution
The way I see the problem, it can only be solve by somehow binary search the array
but I don't based on what should I order it so that I can find the optimal solution without iterating trough the whole array
so better use the formula itself as the key and pair as its value
Better not to use the extra time and complexity that using a map would introduce. The linear search is more efficient than your proposed solution in terms of both complexity and memory.
My initial thoughts are that you might need to sort by the ratio of x:y (and perhaps the value of the smallest of the pair), but I haven't really had the chance to think it through.