2023蓝桥杯C/C++ B组原题https://www.acwing.com/problem/content/4964/
题目描述
$n$ 个人参加一场舞会,每个人的性别(男或女)已知。
在开始跳舞之前,需要先给他们进行配对。
初始时,这 $n$ 个人从左到右排成一队,依次编号为 $1$∼$n$。
其中,第 $i$ 个人的舞蹈水平为 $ai$。
当队列中有男有女时,重复以下过程,进行配对:选出当前队列中彼此相邻且舞蹈水平差异最小的一对男女,让他们组成一对舞伴,并离开队列。
注意:
-
当满足彼此相邻且舞蹈水平差异最小的男女不止一对时,选择最靠左的一对男女进行配对。
-
队伍始终都是连续的,当一对男女离开队列后,剩下的人会紧缩队伍,保证队伍的连贯。
请你计算,一共可以产生多少对配对,并按配对的产生顺序,将所有配对依次输出。
样例
7
BGBGBGB
5 1 2 5 1 2 1
输出
3
2 3
1 4
5 6
思路
通过链表维护前驱和后继 $O(1)$,通过优先队列获取当前队列中相邻水平差异最小值 $O(1)$
算法1
(双向链表+优先队列) $O(n)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5+10;
priority_queue<pair<int,PII>,vector<pair<int,PII>>, greater<pair<int,PII>>> q;
int n,power[N];
bool sex[N];//true表示男
char ch[N];
struct node{
int idx,pre,next;
}point[N];
bool st[N];
vector<PII> vec;
void init(){
for(int i=1;i<=n;i++){
point[i]={i,i-1>=1?i-1:-1,i+1<=n?i+1:-1};
}
}
int main(){
scanf("%d%s",&n,ch+1);
init();
for(int i=1;i<=n;i++)
sex[i]=ch[i]=='B';
for(int i=1;i<=n;i++){
scanf("%d",&power[i]);
if(i>1&&sex[i]!=sex[i-1]) q.push({abs(power[i]-power[i-1]),{i-1,i}});
}
while(q.size()){
auto t=q.top();
q.pop();
int x=t.second.first,y=t.second.second;
if(st[x]||st[y]) continue;
vec.push_back(t.second);
st[x]=true;
st[y]=true;
int px=point[x].pre,py=point[y].next;
if(px!=-1) point[px].next=point[y].next;
if(py!=-1) point[py].pre=point[x].pre;
if(px!=-1&&py!=-1&&sex[px]!=sex[py]){
q.push({abs(power[px]-power[py]),{px,py}});
}
}
printf("%d\n",vec.size());
for(int i=0;i<vec.size();i++){
printf("%d %d\n",vec[i].first,vec[i].second);
}
return 0;
}