【输入】 第一行为正整数n (1≤n≤2×1 05)：队伍中的人数。下一行包含n个字符B或者G，B代表男，G代表女。下一行为n个整数ai(a i≤107)。所有信息按照从左到右的顺序给出。在50％的数据中，n≤2 0 0。 【输出】 第一行：出列的总对数k。接下来输出k行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号(按输入顺序从左往右1至n编号)。请先输出较小的整数，再输出较大的整数。 【样例输入】 4 BGBG 4 2 4 3 【样例输出】 2 3 4 1 2 这周二写了3节课终于写出来了。这道题据说是可以用平衡树做的，但由于平衡树写出来过于麻烦，我就没去试。我使用了一个堆来存储每一对相邻异性的舞蹈技能相差值及两人的编号，每次取出堆顶，判断堆顶的两人是否都已经出列或者已有一人出列，如果是的话继续删除堆顶，直到取到一对合适的异性（^_^），然后输出并删除堆顶。接下来把两人标记为已出队，并将可能形成的新的异性对插入堆。 需要注意的是堆应该是双关键字的，以编号大小为第二关键字（技能差值相同时需要最左边的出列），建立一个小根堆。C++中可以用algorithm里面的heap，也可以用priority_queue。总之有了STL，堆的编写是相当方便的。还有就是关于标记某人是否出列以及寻找该人左右的人，标程用的双向链表，但我认为没有必要，可以直接用数组来记录，方便快捷只是空间稍大。 具体内容详见代码： View Code 1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<iostream> 5 #include<vector> 6 7 using namespace std; 8 9 struct node 10 { 11 char sex;int val,l,r,exi; 12 }pdf[200001]; 13 14 struct sb 15 { 16 int l,r,val; 17 }ergo[200001],solu[200001]; 18 19 char sex[200001];int p=0,n; 20 21 bool cmp(sb a,sb b) 22 { 23 if(a.val==b.val) return a.l>b.l; 24 else return a.val>b.val; 25 } 26 27 inline void del(int i) 28 { 29 if(pdf[i].l>=0) pdf[pdf[i].l].r=pdf[i].r; 30 if(pdf[i].r<=n-1) pdf[pdf[i].r].l=pdf[i].l; 31 pdf[i].exi=0; 32 } 33 34 int main() 35 { 36 freopen("DancingLessons.in","r",stdin); 37 freopen("DancingLessons.out","w",stdout); 38 39 scanf("%d",&n); 40 scanf("%s",sex); 41 for(int i=0;i<n;i++) pdf[i].sex=sex[i]; 42 43 for(int i=0;i<n;i++) 44 { 45 int tmp; 46 scanf("%d",&tmp); 47 pdf[i].l=i-1; 48 pdf[i].r=i+1; 49 pdf[i].exi=1; 50 pdf[i].val=tmp; 51 52 if(i!=0&&pdf[i].sex!=pdf[i-1].sex) 53 { 54 ergo[++p].val=abs(pdf[i].val-pdf[i-1].val); 55 ergo[p].l=i-1,ergo[p].r=i; 56 } 57 } 58 make_heap(&ergo[1],&ergo[p+1],cmp); 59 60 int sol=0; 61 while(p>=1) 62 { 63 sb k=ergo[1],k2; 64 while((!(pdf[k.l].exi&&pdf[k.r].exi))&&p>=1) pop_heap(&ergo[1],&ergo[p+1],cmp),p--,k=ergo[1]; 65 if(p==0) break; 66 67 solu[++sol]=k; 68 if(pdf[k.l].l>=0&&pdf[k.r].r<=n-1) 69 if(pdf[pdf[k.l].l].sex!=pdf[pdf[k.r].r].sex) 70 { 71 k2.l=pdf[k.l].l;k2.r=pdf[k.r].r; 72 k2.val=abs(pdf[pdf[k.l].l].val-pdf[pdf[k.r].r].val); 73 74 ergo[p+1]=k2; 75 push_heap(&ergo[1],&ergo[p+2],cmp);p++; 76 } 77 78 del(k.l);del(k.r); 79 } 80 81 printf("%d\n",sol); 82 for(int i=1;i<=sol;i++) 83 printf("%d %d\n",solu[i].l+1,solu[i].r+1); 84 85 return 0; 86 }
转载于:https://www.cnblogs.com/stickjitb/archive/2012/05/26/2519525.html
