社区讨论

0pts WA求助

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@loo4ji44
此快照首次捕获于
2023/11/07 17:23
2 年前
此快照最后确认于
2023/11/07 19:23
2 年前
查看原帖
样例正确
但提交全WA
可能是题意理解有误(关于怎么样才是最左侧的一对)?
CPP
/*定义一个结构体,里面存储编号,左侧的人的编号,右侧的人的编号,自己的性别
优先队列使用二元组,小根堆,q2为编号,q1为差值 
一次for循环,寻找第i个和第i+1个性别不同的人,并将第i个中的差值和第i个人的编号放入优先队列。
一次while循环,直到队列为空。将堆顶取出,输出编号和下一个人的编号,然后让此人左侧的人的 右侧编号变为 输出的那个人下一个人的右侧编号
如果新组成的两人性别不同,则计算两人的差值,将其和左侧的人编号放入优先队列 
*/
#include<bits/stdc++.h>
using namespace std;
struct people{
	int num,left_num,right_num;
	char sex;
}st[200009];
int n;
int a[200009];
bool tag[200009];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>st[i].sex;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) st[i].num=i;
	for(int i=1;i<=n;i++) st[i].left_num=i-1;
	for(int i=1;i<=n;i++) st[i].right_num=i+1;
/*	for(int i=1;i<=n;i++){
		cout<<st[i].left_num<<" "<<st[i].num<<" "<<st[i].right_num<<" "<<st[i].sex<<endl;
	} */
	for(int i=1;i<=n;i=st[i].right_num){
		if(st[i].sex+st[st[i].right_num].sex==('B'+'G')){
			q.push(make_pair(abs(a[st[i].num]-a[st[i].right_num]),st[i].num));
		}
	}
	while(!q.empty()){
		int x=q.top().second;
		int y=st[x].right_num;
		if(tag[x]==0&&tag[y]==0&&st[x].sex+st[y].sex==('B'+'G')) cout<<x<<" "<<y<<endl;
		q.pop();
		if(tag[x]==1||tag[y]==1) continue;
		tag[x]=1,tag[y]=1;
		st[st[x].left_num].right_num=st[y].right_num;
		st[st[y].right_num].left_num=st[x].left_num;
		int l=st[x].left_num,r=st[y].right_num;
		if(st[l].sex+st[r].sex==('B'+'G')){
			//cout<<l<<" "<<r<<endl; 
			q.push(make_pair(abs(a[l]-a[r]),st[l].num));
		}
	}
	return 0;
}

回复

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

正在加载回复...