社区讨论
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 条回复,欢迎继续交流。
正在加载回复...