P1878舞蹈课
思路
这道题难就难在体面容易理解，但代码写起来很棘手（我是说手写堆），先简单看一下体面，抓取重点：
1.当这一排中至少有一对相邻的异性
2.舞蹈技术相差最小的那一对出列
3.最左边的那一对先出列
4.队伍中的空白按原顺序补上
描述中说模拟，确实是模拟，怎么模拟呢？ 过程如下：
1.先建一个Bool数组（或者Char数组），用于存放性别
2.输入舞蹈技术值，同时将一对异性入堆（入堆的是舞蹈技术相差）
3.取出堆顶那一对人（理由：小根堆中根最小）
4.保证此时堆顶那一对人不是已经出堆的人
5.讲不上后的队伍再次取出一对异性入堆
6.重复3、4、5，直到堆为空
7.输出
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
const int maxn = 200010;
struct node
{
int value,l,r;
friend bool operator > (node aa,node bb){return aa.value > bb.value || (aa.value == bb.value && aa.l > bb.l);}
//重载运算符，根据题意，技术值差的先出堆，如果值相同，则先左（即l越小）
}heap[maxn],tmp;
void swap(node &a,node &b){tmp = a,a = b,b = tmp;}
int n,a[maxn],heap_size,tot,tl[maxn],tr[maxn];
bool b[maxn],f[maxn];
void put(int value,int l,int r){
int now = ++heap_size,next;
heap[heap_size].value = value,heap[heap_size].l = l,heap[heap_size].r = r;
while(now > 1){
next = now >> 1;
if(heap[now] > heap[next]) return;
swap(heap[now],heap[next]);
now = next;
}
}
void get(){
int now = 1,next;
heap[1].value = heap[heap_size].value,heap[1].l = heap[heap_size].l,heap[1].r = heap[heap_size--].r;
while(now << 1 <= heap_size){
next = now << 1;
if(next < heap_size && heap[next] > heap[next + 1]) next++;
if(heap[next] > heap[now]) return;
swap(heap[now],heap[next]);
now = next;
}
}
//日常堆操作
int main(){
scanf("%d\n",&n);
for(int i = 0;i < n;i++){
char ch = getchar();
f[i] = ch == 'B';//若这个人他是'B'置f[i]为true,反之亦反
}//巧妙地输入情况
for(int i = 0;i < n;i++){
scanf("%d",&a[i]);//输入舞蹈技术
int j = i - 1;//置j为i前面那个人
if(i && f[i] ^ f[j]) put(abs(a[i] - a[j]),j,i);
//如果i不是指向第一个人，且f[i] != f[j]，将舞蹈技术值差和两个人的下标入堆
}
while(heap_size){
int l = heap[1].l,r = heap[1].r,ll,rr;//当前最小的那一对出堆
b[l] = b[r] = true;//置他们为出堆状态
tl[++tot] = l + 1,tr[tot] = r + 1;//将他们的下标存入数组，tot+1
do{
get();//出堆操作
if(!heap_size) break;//如果堆空就退出
ll = heap[1].l,rr = heap[1].r;
}while(b[ll] || b[rr]);
//此操作维护该堆直至堆顶不为已出堆的元素
while(l >= 0 && b[l]) l--;
while(r < n && b[r]) r++;
//寻找空白两边的元素,相当于按原顺序补上
if(l >= 0 && r < n && f[l] ^ f[r]) put(abs(a[l] - a[r]),l,r);//将其入堆
}
printf("%d",tot);
for(int i = 1;i <= tot;i++) printf("\n%d %d",tl[i],tr[i]);
//输出答案
return 0;
}