社区讨论

!!求助求助!!悬关

P1878舞蹈课参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m62z547y
此快照首次捕获于
2025/01/19 10:04
去年
此快照最后确认于
2025/11/04 11:20
4 个月前
查看原帖
思路清晰,但是不知道哪里有问题
CPP
#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;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...