!!求助求助!!悬关
  • 板块P1878 舞蹈课
  • 楼主XYY62012
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/19 10:03
  • 上次更新2025/1/19 12:16:14
查看原帖
!!求助求助!!悬关
1108111
XYY62012楼主2025/1/19 10:03

思路清晰,但是不知道哪里有问题

#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;
}
2025/1/19 10:03
加载中...