描述 Description
有 n 个人参加一个舞蹈课。每个人的舞蹈技术由整数 来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果相差最小的不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为 ABCD，那么 BC 出列之后队伍变为 AD）。舞蹈技术相差最小即是 的绝对值最小。
你的任务是，模拟以上过程，确定跳舞的配对及顺序。
输入格式 InputFormat
第一行为正整数 ：队伍中的人数 n(1<=n<=2*10^5)。
下一行包含 n 个字符 B 或者 G，B 代表男，G 代表女。
下一行为 n 个整数 ai(ai<=10^7)。所有信息按照从左到右的顺序给出。
输出格式 OutputFormat
第一行：出列的总对数 k。
接下来输出 k 行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右 1 至 n 编号）。请先输出较小的整数，再输出较大的整数。
样例输入 SampleInput
4
BGBG
4 2 4 3
样例输出 SampleOutput
2
3 4
1 2
代码 Code
采用（数组模拟）链表维护队列中的前后顺序，优先队列维护男女出列顺序。然后就是按照题目模拟就行了。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct dancer
{
int idx,idy,dif;
bool operator > (const dancer &temp) const
{
if (dif!=temp.dif) return dif>temp.dif;
else if (idx!=temp.idx) return idx>temp.idx;
else if (idy!=temp.idy) return idy>temp.idy;
}
};
struct answer
{
int x,y;
}ans[200005];
bool used[200005];
int a[200005],pre[200005],nxt[200005];
char c[200005];
priority_queue < dancer , vector<dancer> , greater<dancer> > q;
int sum,tx,ty;
dancer tmp;
int main()
{
read(n);
scanf("%s",c+1);
for (i=1;i<=n;i++)
{
read(a[i]);
if (i>1 && c[i]!=c[i-1]) q.push((dancer){i-1,i,abs(a[i]-a[i-1])});
}
for (i=1;i<=n;i++) pre[i]=i-1,nxt[i]=i+1;
memset(used,false,sizeof(used));
memset(ans,0,sizeof(ans));
sum=0;
while (!q.empty())
{
tmp=q.top();q.pop();
if (!used[tmp.idx] && !used[tmp.idy])
{
used[tmp.idx]=used[tmp.idy]=true;
nxt[pre[tmp.idx]]=nxt[tmp.idy];
pre[nxt[tmp.idy]]=pre[tmp.idx];
ans[++sum].x=tmp.idx;
ans[sum].y=tmp.idy;
}
tx=pre[tmp.idx];ty=nxt[tmp.idy];
if (tx>0 && ty<=n && c[tx]!=c[ty] && !used[tx] && !used[ty]) q.push((dancer){tx,ty,abs(a[tx]-a[ty])});
}
printf("%d\n",sum);
for (i=1;i<=sum;i++) printf("%d %d\n",ans[i].x,ans[i].y);
return 0;
}