【NOIP模拟赛】舞蹈课

2014年9月13日1,5070

问题描述

有n个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始,他们从左到右站成一排。当这一排中至少有一对相邻的异性时,舞蹈技术相差最小的那一对会出列并开始跳舞。如果相差最小的不止一对,那么最左边的那一对出列。一对异性出列之后,队伍中的空白按原顺序补上(即:若队伍为ABCD,那么BC出列之后队伍变为AD)。舞蹈技术相差最小即是的绝对值最小。

你的任务是,模拟以上过程,确定跳舞的配对及顺序。

输入

第一行为正整数n<=200000:队伍中的人数。下一行包含n个字符B或者G,B代表男,G代表女。下一行为n个整数ai<=10^7。所有信息按照从左到右的顺序给出。在50%的数据中,n<=200。

输出

第一行:出列的总对数k。接下来输出k行,每行是两个整数。按跳舞顺序输出,两个整数代表这一对舞伴的编号(按输入顺序从左往右1至n编号)。请先输出较小的整数,再输出较大的整数。

样例输入

4

BGBG

4 2 4 3

样例输出

2

3 4

1 2

样例输入

4

BGBB

1 1 2 3

样例输出

1

1 2

题解

直接暴力有50分。。。

每次用for找最小值,然后标记一下

100分做法直接搞个堆找最小值。。然后用链表维护删除即可