- 一本通传送门
- 可以注意到，如果建立两个堆，分别比较大小可能会存在重复的情况，所以问题的关键就在于如法避免重复。下面提供两种方法。
方法1
- 想要做到不重复，首先想到加编号，用来记录是否已支付
- 那么看N·M=1500000，不会爆，可以一试
#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > a;
priority_queue<pair<int,int> > b;
bool f[1500010];
int main()
{
int n,m,k=0,x;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
for(int j=1;j<=m;j++){
scanf("%d",&x);
a.push(make_pair(x,++k));//k是唯一编号，配合f数组记录
b.push(make_pair(x,k));
}
pair<int,int> y;
while(f[a.top().second])//已支付的出堆
a.pop();
y=a.top();
printf("%d ",y.first);
f[y.second]=1;//标记
//以下是输出当前最大值，基本同上
while(f[b.top().second])
b.pop();
y=b.top();
printf("%d\n",y.first);
f[y.second]=1;
}
return 0;
}
方法2
- 换一种思路，既然正常的堆打着比较麻烦，那就要善用STL。
- 当当当当——multiset
- 下附常见用法
- 这样就可以简单粗暴地过啦
#include<bits/stdc++.h>
using namespace std;
multiset<int> q;
int n,m,x,f;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
for(int j=1;j<=m;j++){
scanf("%d",&x);
q.insert(x);
}
printf("%d ",*q.begin());
q.erase(q.begin());
printf("%d\n",*(--q.end()));
q.erase((--q.end()));
}
return 0;
}
- 另，还可以看看大佬的题解
multiset常见用法备忘
建立：multiset<数据类型> 变量名;//例：multiset<int> q;
插入：变量名.insert(插入变量);//例：q.insert(x);
判断是否为空：变量名.empty() //空返回1
删除：变量名.erase(删除的变量);//例：q.erase(q.begin());
最小值：变量名.begin()
最大值：变量名.end()
//注意begin()和end()都是取地址，需要具体值的时候在前面加*
//另外，用end()需要-1
最后挂个链接
碎碎念
- 又是几周没刷题
- 啊……心慌慌
- 以后尽量（握拳
