I just want to use priority queue with pair of integers such that it stores the maximum product of 2 numbers in descending order . How can i use it in C++ .
For Eg : —
2 5
5 10
3 6
will be save in priority queue as
5 10
3 6
2 5
and if a clash happen , then the first element should be prefer .
Also I was solving this problem using priority queue but getting WA at case 30 , strange RUNTIME error for comparison but it passes using vector of pairs . I just found on the net on how to write custom comparison function for priority queue . Is there any other method without using class or struct .
Instead of defining class / struct expilictly, you can use lambda expression as a comparator: example
Can you tell me what's wrong with my this solution . It is same as my accepted solution using vector of pairs .
You need to modify the condition inside the while loop from
while(n!=0)towhile(n!=0 && !pq.empty()), because there can be the situation when the burglar can steal more matchboxes than there is in the warehouse.return a.first * a.second < b.first * b.second || (a.first * a.second == b.first * b.second && a.first < b.first);
Should't the sign should be changed i.e > . I know it will give opposite result . But as far as i know that if we have to keep 1'st preference than we should return true in c++ ? . Here is the same code with opposite sign implemented on vector of pairs . link
Documentation
Note that the default comparator is
std::less<T>but as stated in the documentation,std::priority_queue"provides constant time lookup of the largest (by default) element".So for
std::vectoryou are right, the sign needs to be changed, but forstd::priority_queueit shouldn't because the top element of the priority queue is the greatest one (with respect to your comparison function). For an instance, if your comparison function isp1.first * p1.second < p2.first * p2.secondthen the top element of thestd::priority_queuewould be one of the elements with greatest product. And if you need to choose among of them the one having the greatestfirstvalue you need to add this condition to the comparator:|| (p1.first * p1.second == p2.first * p2.second && p1.first < p2.first).