我想要一个优先级队列,这样首先应该根据第一个元素(递增顺序(完成,当发生冲突时,然后基于第二个元素(递减顺序(。我想出了以下代码:
#include<bits/stdc++.h>
using namespace std;
struct Compare {
constexpr bool operator()(pair<int, int> const & a,
pair<int, int> const & b) const noexcept
{ return a.first > b.first || (a.first == b.first && a.second < b.second); }
};
int main()
{
priority_queue<pair<int,int>,
std::vector<pair<int,int> >,
Compare> Q;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
Q.push(make_pair(a,b));
}
for(int i=1;i<=n;i++)
{
pair<int,int> m;
m=Q.top();
if(m.first <= i)
cout<<m.first<<" "<<m.second<<"n";
Q.pop();
}
}
问题是在 for 循环中,我希望该对在所有满足条件的对中处于顶部:
pair<ll,ll> m;
m.first <= i
例如 -
N=8, Pairs :
1 100
1 300
2 500
4 800
3 500
4 100
8 1000
2 700
然后是以下代码:
for(int i=1;i<=n;i++)
{
pair<int,int> m;
m=Q.top();
cout<<m.first<<" "<<m.second<<"n";
// Q.pop();
}
应给出以下结果:
1 300 (for i=1, it should have 2 choices : (1,100),(1,300) and select (1,300) )
2 700 (for i=2 it should have 4 choices : (1,100),(1,300),(2,500),(2,700) and select (2,700))
2 700 (for i=3 it should have 5 choices : (1,100),(1,300),(2,500),(2,700),(3,500) and select (2,700))
4 800 (for i=4,5,6,7 it should have 7 choices : (1,100),(1,300),(2,500),(2,700),(3,500),(4,100),(4,800) and select (4,800)).
8 1000 (for i=8 it should have 8 choices : (1,100),(1,300),(2,500),(2,700),(3,500),(4,100),(4,800),(8,1000) and select (8,1000)).
我希望这个例子现在已经清楚了。
问题是Priority_Queue
根据我的Compare
函数优先考虑第一个元素,因此它选择(1 300)
而不是(2 700)
来i=2,3
。
我应该怎么做才能使用 for 循环的迭代器更改优先级队列中的顶部元素?有人可以帮助我吗?
What should I do to change the top element in Priority Queue
如果更改不影响顺序,只需修改Q.top()
即可。
如果更改可能会影响订单,请Q.push()
修改后的Q.pop()
。