有 $n$ 个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为 ABCD，那么 BC 出列之后队伍变为 AD）。舞蹈技术相差最小即是 $a_i$ 的绝对值最小。
任务是模拟以上过程，确定跳舞的配对及顺序。
第一行一个正整数 $n$ 表示队伍中的人数。
第二行包含 $n$ 个字符 B 或者 G，B 代表男，G 代表女。
第三行为 $n$ 个整数 $a_i$。所有信息按照从左到右的顺序给出。
第一行一个整数表示出列的总对数 $k$。
接下来 $k$ 行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右 $1$ 至 $n$ 编号）。请先输出较小的整数，再输出较大的整数。
4 BGBG 4 2 4 3
2 3 4 1 2
对于 $50\%$ 的数据，$1\leq n\leq 200$。
对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\le a_i\le 10^7$。
#include <bits/stdc++.h> using namespace std; struct node { int l, r, cha, num; bool judge; // 打男女标记！ } a[200010]; int ans[200010][2], sum = 0, n, now, t = 0; char c; priority_queue<node> q; // 用优先队列来维护相邻舞者之间的技术值的差，每次取最小 bool operator<(node R, node L) { // 重载运算符，便于后续判断 int tl = abs(L.cha), tr = abs(R.cha); // 优先队列有限法则 if (tr != tl) return tl < tr; else return L.num < R.num; } int main() { int next; cin >> n; for (int i = 1; i <= n; i++) { cin >> c; if (c == 'B') a[i].judge = 0; else a[i].judge = 1; } scanf("%d", &now); for (int i = 1; i < n; i++) { scanf("%d", &next); a[i].num = i; // 自身是第几个 a[i].cha = next - now; // 预处理技术值差 a[i].l = i - 1; // 预处理左右 a[i].r = i + 1; q.push(a[i]); now = next; } a[n].r = n + 1; a[n].num = n; a[n].cha = 0x7f; // 开始模拟过程 while (!q.empty()) { int x1 = q.top().num, cmp = q.top().cha, x2 = a[x1].r; q.pop(); // 在此时，非法的一队就会被丢弃 if (a[x1].cha == cmp // 判断是否更新过 && a[x1].judge != a[x2].judge // 判断是否一男一女 && x1 != 0 && x2 != n + 1) { // 特判链表首尾 // 在每次更新差值的时候，用int数组存放更新了的差值. // 如果在后面从优先队列中取出的差值与之前存放的差值不相等 // 则说明这个差值未被更新，那也不执行操作 t++, ans[t][0] = x1, ans[t][1] = x2; a[a[x1].l].cha += a[x1].cha + a[x2].cha; // 更新差值 a[a[x2].r].l = a[x1].l; // 断链重连 a[a[x1].l].r = a[x2].r; if (a[x1].l > 0 && a[x2].r <= n) // if合法, 入队 q.push(a[a[x1].l]); // tip:再次特判了链表首尾 a[x1].l = a[x1].r = 0; a[x2].l = a[x2].r = n + 1; } } cout << t << endl; for (int i = 1; i <= t; i++) printf("%d %d\n", ans[i][0], ans[i][1]); // NO TLE // cout << ans[i][0] << ' ' << ans[i][1] << endl; return 0; }