双向链表+自定义堆排序
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
const int N=2e5+10;
int l[N],r[N],w[N],n;
bool st[N]; //定义是否被
char s[N];
vector<PII>res; //存储答案
struct node{
int val,x,y;
friend bool operator<(const node a,const node b){
if(a.val!=b.val) return a.val>b.val;
return a.x>b.x; //相同权值按照下标从小到大排序
}
};
int main()
{
cin>>n>>s+1;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=1;i<=n;i++){ //初始化左边的数
l[i]=i-1;
r[i]=i+1;
}
priority_queue<node>heap;
for(int i=1;i<n;i++){
if(s[i+1]!=s[i]){
int w1=abs(w[i+1]-w[i]);
heap.push({w1,i,i+1});
}
}
while(heap.size()&&r[0]!=n+1){ //队列和堆均不为空
auto [val,x,y]=heap.top();heap.pop();
if(st[x]||st[y])continue;
st[x]=st[y]=true;
res.push_back({x,y});
if(r[y]<=n&&l[x]>=1&&s[r[y]]!=s[l[x]]){
int w1=abs(w[r[y]]-w[l[x]]);
heap.push({w1,l[x],r[y]});
}
r[l[x]]=r[y];
l[r[y]]=l[x];
}
cout<<res.size()<<endl;
for(auto &t:res){
cout<<t.x<<" "<<t.y<<endl;
}
return 0;
}