舞蹈课-题解

题目来源：NOI导刊

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

输入：
第一行为正整数n (1≤n≤2×10^5)，表示队伍中的人数。
下一行包含n个字符B或者G，B代表男，G代表女。
下一行为n个整数ai(ai≤10^7)。所有信息按照从左到右的顺序给出。

输出：
第一行输出出列的总对数，下面N行，每行输出两个整数，按照跳舞顺序输出，表示一对舞伴。两个数小的在前。

观察到，一对舞伴出列后，原来不相邻的两个人就会相邻，因此考虑使用链表。又发现题目要求多次取出最小值，并且在取的过程中还可能插入数据，因此考虑用最小堆实现。
在写堆的删除操作时要格外小心，删除后还必须保证堆的性质。

代码如下：

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#include <assert.h>
#define INF 2000000000
#define MAXN 200005

#define rc(x) (((x) << 1) + 2)
#define lc(x) (((x) << 1) + 1)
#define pa(x) (((x) - 1) >> 1)

typedef struct element
{
   long v,num;
}node;

node heap[MAXN * 2 + 10];
long heapsize = 0;
long back[MAXN];   //a person's position in the heap

long v[MAXN],prev[MAXN],next[MAXN];
int inheap[MAXN];
char gender[MAXN];
long N,pair,g,b;

inline int smaller(node a,node b)
{
   if(a.v < b.v)    return 1;
   else if(a.v == b.v && a.num < b.num)    return 1;
   return 0;
}

inline void lswap(long *a,long *b)
{
   long tmp = *a;
   *a = *b;*b = tmp;
}

inline void nswap(node *a,node *b)
{
   node tmp = *a;
   *a = *b;*b = tmp;
}

void heap_insert(long v,long num)   //v:difference num:position in line
{
   inheap[num] = 1;
   long t = heapsize;
   heap[t].v = v;
   heap[t].num = num;
   back[num] = t;
   heapsize ++;
   while(t > 0 && smaller(heap[t],heap[pa(t)]))   //moveup
   {
       lswap(&back[heap[t].num],&back[heap[pa(t)].num]);
       nswap(heap + t,heap + pa(t));
       t = pa(t);
   }
}

void heapfy(long p)   //move down if necessary
{
   long s = p;
   while(1)
   {
       if(lc(p) < heapsize && smaller(heap[lc(p)],heap[s]))    s = lc(p);
       if(rc(p) < heapsize && smaller(heap[rc(p)],heap[s]))    s = rc(p);
       if(s != p)
       {
           lswap(back + heap[s].num,back + heap[p].num);
           nswap(heap + s,heap + p);
           p = s;
       }
       else    break;
   }
}

void heap_remove(long p)   //be careful here
{
   //fprintf(stderr,"remove %ld %ld\n",p,heap[p].num);
   //assert(inheap[heap[p].num]);
   heapsize --;
   inheap[heap[p].num] = 0;
   //back[heap[p].num] = -1;
   back[heap[heapsize].num] = p;
   heap[p] = heap[heapsize];
   heap[heapsize].num = heap[heapsize].v = INF;
   if(p < heapsize && p > 0 && smaller(heap[p],heap[pa(p)]))   //rememeber to check whether p is out of current range
   {
       while(p > 0 && smaller(heap[p],heap[pa(p)]))
       {
           lswap(&back[heap[p].num],&back[heap[pa(p)].num]);
           nswap(heap + p,heap + pa(p));
           p = pa(p);
       }
   }
   else
       heapfy(p);
}

void init()
{
   long i;
   g = b = 0;
   scanf("%ld\n",&N);
   scanf("%s\n",gender);
   for(i = 0;i < N;i ++)
   {
       scanf("%ld",&v[i]);
       //alive[i] = 1;
       if(gender[i] == 'G')    g ++;
       else if(gender[i] == 'B')    b ++;
       next[i] = i + 1;
       prev[i] = i - 1;
   }
   for(i = 0;i < N - 1;i ++)
       if(gender[i] != gender[i + 1])
           heap_insert(labs(v[i + 1] - v[i]),i);
   prev[0] = next[N - 1] = -1;
}

void go_out(long num)
{
   //assert(next[num] != -1);
   //assert(alive[num]);
   //assert(alive[next[num]]);
   printf("%ld %ld\n",num+1,next[num]+1);
   //alive[num] = alive[next[num]] = 0;
   heap_remove(0);
   if(inheap[next[num]])   //remove only when next[num] is in the heap or you'll remove sth else
       heap_remove(back[next[num]]);
   if(prev[num] != -1)
   {
       next[prev[num]] = next[next[num]];
       if(inheap[prev[num]])
           heap_remove(back[prev[num]]);
   }
   if(next[next[num]] != -1)
   {
       prev[next[next[num]]] = prev[num];
       if(prev[num] != -1 && gender[prev[num]] != gender[next[next[num]]])
           heap_insert(labs(v[prev[num]] - v[next[next[num]]]),prev[num]);
   }
}

void check_heap(long p)
{
   if(back[heap[p].num] != p)    printf("B:%ld\n",p);
   if(p > 0 && smaller(heap[p],heap[pa(p)]))    printf("A:%ld\n",p);
   if(rc(p) < heapsize)    check_heap(rc(p));
   if(lc(p) < heapsize)    check_heap(lc(p));
}

void solve()
{
   node min;
   pair = (g < b) ? g : b;
   printf("%ld\n",pair);
   while(pair --)
   {
       //check_heap(0);
       min = heap[0];
       go_out(min.num);
   }
}

int main()
{
   freopen("dancinglessons.in","r",stdin);
   freopen("dancinglessons.out","w",stdout);
   init();
   solve();
   fclose(stdout);
   return 0;
}