0pts WA求助
  • 板块P1878 舞蹈课
  • 楼主strategy
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/7 17:23
  • 上次更新2023/11/7 19:23:07
查看原帖
0pts WA求助
292352
strategy楼主2023/11/7 17:23

样例正确

但提交全WA

可能是题意理解有误(关于怎么样才是最左侧的一对)?

/*定义一个结构体,里面存储编号,左侧的人的编号,右侧的人的编号,自己的性别
优先队列使用二元组,小根堆,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;
}
2023/11/7 17:23
加载中...