Skip to content

1129: 拉丁舞课配对

题目

题目描述

有n个同学体育课选择了拉丁舞课。每个人的拉丁舞水平是一个整数。一开始,他们从左到右站成一排。当这一排中至少有一对相邻的异性时,水平相差最小的那一对会出列并开始跳舞。如果不止一对,那么最左边的那一对出列。一对异性出列之后,队伍中的空白按原顺序补上(即:若队伍为ABCD,那么BC出列之后队伍变为AD)。

给出以上信息,请确定配对及顺序。

注意:本题可以使用STL

输入格式

第一行为正整数$n(1<=n<=2*10^5)$:队伍中的人数。

下一行包含n个字符B或者G,B代表男,G代表女。

下一行为n个整数$ai(ai<=10^7)$。

所有信息按照从左到右的顺序给出。在50%的数据中,n<=200。

输出格式

第一行:出列的总对数k。

接下来输出k行,每行是两个整数。按跳舞顺序输出,两个整数代表这一对舞伴的编号(按输入顺序从左往右1至n编号)。

请先输出较小的整数,再输出较大的整数。

样例输入

text 4 BGBG 4 2 4 3

样例输出

text 2 3 4 1 2

数据范围

不用理会数据范围,使用堆做这道题即可AC!

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!