思路清晰,但是不知道哪里有问题
#include<bits/stdc++.h>
using namespace std;
const int N=590021;
int n,sum;
char x;
int out[N]={1};
int gender[N],num[N];//性别,舞蹈技术
int left[N],right[N];//建立链表
struct node{
int l;
int r;
}p[N];
struct dui{
int l;//左边的人
int r;//右边的人
int cha;//两者舞蹈技术之差
bool operator>(const dui &x) const {//如果出现两个相同的最小值,只输出其中一个
if (cha!=x.cha) {
return cha>x.cha;
}
return l>x.l;
}
};
dui ans[N];
priority_queue<dui,vector<dui>,greater<dui>> q;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
if(x=='B'){
gender[i]=0;//男生
}else{
gender[i]=1;//女生
}
}
for(int i=1;i<=n;i++){
cin>>num[i];
}
for(int i=1;i<=n;i++){
p[i].l=i-1;
p[i].r=i+1;
}
p[1].l=1;
p[n].r=n;
for(int i=1;i<=n;i++){
if(gender[i]!=gender[i+1]){
dui v;
v.cha=abs(num[i]-num[i+1]);
v.l=i,v.r=i+1;
q.push(v);//存储
}
}
while(!q.empty()){
dui u=q.top();
if(out[u.l]==0 || out[u.r]==0){//特判是否出队
q.pop();
continue;
}
ans[++sum]=u;
out[u.l]=0;
out[u.r]=0;//标记已出队
q.pop();//出队 (链表断开
int a=p[u.l].l;
int b=p[u.r].r;
p[a].r=b;
p[b].l=a;//重新连接链表
if(gender[a]!=gender[b]){
dui t;
t.l=a;
t.r=b;
t.cha=abs(num[a]-num[b]);
q.push(t);
}
}
cout<<sum<<endl;
for(int i=1;i<=sum;i++){
cout<<ans[i].l<<' '<<ans[i].r<<endl;
}
return 0;
}