题解 P1878 【舞蹈课】
sukimo
2020-07-24 13:13:50
首先，两两配出的对子是有明显的优先级的，而且会出现跳完了这对删除和删除后队列拼接加入新配对这两种操作，于是想到使用堆来维护。跳完了删除，还需要灵活的维护接下来新队伍拼接后是哪两个挨在一起，于是使用链表。读入时先将所有配对入堆，选出跳舞的一对，出堆并打标记，站位拼接处理新对。重复以上即可。
```
#include<bits/stdc++.h>
using namespace std;
const int MX=200005;
struct STR1{int q1,q2,_abs;};struct STR2{char sex;int le,ri,val;}dance[MX];
bool operator <(STR1 a,STR1 b){return a._abs==b._abs?a.q1>b.q1:a._abs>b._abs;}
STR1 pack(int q1,int q2,int _abs){STR1 a;a.q1=q1;a.q2=q2;a._abs=_abs;return a;}
int vis[MX];priority_queue<STR1>heap;
void solve(int x,int y){
vis[x]=vis[y]=1;heap.pop();
if(dance[x].le!=-1)dance[dance[x].le].ri=dance[y].ri;
if(dance[y].ri!=-1)dance[dance[y].ri].le=dance[x].le;
if(dance[x].le!=-1&&dance[y].ri!=-1&&dance[dance[x].le].sex!=dance[dance[y].ri].sex)heap.push(pack(dance[x].le,dance[y].ri,abs(dance[dance[x].le].val-dance[dance[y].ri].val)));
}
int main(){
int n,k,girl_cnt=0,boy_cnt=0;scanf("%d",&n);
for(int i=1;i<=n;i++){dance[i].le=(i-1?i-1:-1);dance[i].ri=(n-i?i+1:-1);}
for(int i=1;i<=n;i++){cin>>dance[i].sex;dance[i].sex=='B'?boy_cnt++:girl_cnt++;}
for(int i=1;i<=n;i++){scanf("%d",&dance[i].val);if(i-1&&dance[i].sex!=dance[i-1].sex)heap.push(pack(i-1,i,abs(dance[i].val-dance[i-1].val)));}
k=min(girl_cnt,boy_cnt);printf("%d\n",k);
for(int i=1;i<=k;i++){
while(vis[heap.top().q1]||vis[heap.top().q2])heap.pop();
printf("%d %d\n",heap.top().q1,heap.top().q2);
solve(heap.top().q1,heap.top().q2);
}
return 0;
}
```