优先队列+双向链表第二弹
作者:
梦念小袁
,
2023-06-04 12:36:35
,
所有人可见
,
阅读 164
优先队列
双向链表
原题链接
GBGB 表示男女
1 2 3 4 表示权重
选择权重差距最小的男女 拿出来
然后剩下的接着相邻 直到无法操作
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=2e5+10;
char sex[N];
int w[N],l[N],r[N];// 左右关系的连续性质 使用链表是非常优雅的方式
int n;
bool st[N];// 表示堆中的延迟关系删除
struct code
{
int ans,a,b;
bool operator<(const code&t)const// 重载运算符
{
if(ans!=t.ans) return ans>t.ans;
return a>t.a;// 表示
}
};
priority_queue<code> heap;// 表示大根堆 然后再使用比较大小就是小堆
code get(int x,int y)
{
return {abs(w[x]-w[y]),x,y};
}
void remove(int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
int main()
{
cin>>n>>(sex+1);
for(int i=1;i<=n;i++) cin>>w[i];
w[0]=w[n+1]=1e9;// 表示使用哨兵
for(int i=0;i<=n+1;i++) l[i]=i-1,r[i]=i+1;// 表示链表初始化
for(int i=0;i<=n+1;i++) heap.push(get(i,i+1));
vector<PII> res;
while(!heap.empty())
{
auto t=heap.top(); heap.pop();
auto [_,a,b]=t;
if(st[a]||st[b]) continue;// 表示延迟的删除
if(!a||b==n+1) break;// 表示使用结束
if(sex[a]==sex[b]) continue;// 表示不满足关系的组合
heap.push(get(l[a],r[b]));// 表示加入新的关系
remove(a),remove(b);
st[a]=st[b]=true;
res.push_back({a,b});
}
cout<<res.size()<<endl;
for(auto &[a,b]:res) cout<<a<<" "<<b<<endl;
return 0;
}