舞蹈课（dancinglessons）

洛谷p1878

题目大意

n个人排成一列，给出n个人的性别及a[i]值,每次让a[i]值相差最小的两个异性出列，输出这样的对数及两人的编号。n<=200000。

题解

50分算法

对于第一个问题，只需要输出男生和女生中个数少的那一个，因为最终一定有一方全部出列，不然肯定有男生和女生相邻，就会继续出列。 对于第二个问题，构建一个结构体node，来储存每个人的所有信息。这和约瑟夫问题有异曲同工之妙，我们可以把每个人的位置（编号）作为元素，建立双向链表，于是可以把编号作为node里的下标，知道这个元素的所有信息。链表的好处是可以O(1)时间删除链表中元素，双向的好处是可以方便地找到每个元素的前驱和后继。美中不足的是，每次让最小的一对出列需要扫描整个链表，所以复杂度是O(n^2)。 代码如下。

#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define INF 1000000000 struct node { char c; int data,pre,next; }a[200005]; int n; int main() { cin>>n; int g=0,b=0; for (int i=1;i<=n;i++) { cin>>a[i].c; if (a[i].c=='G') g++; else b++; } for (int i=1;i<=n;i++) { cin>>a[i].data; a[i].pre=i-1; a[i].next=i+1; } a[0].next=1; cout<<min(g,b)<<'\n'; for (int i=1;i<=min(g,b);i++) { int x=a[0].next,y=INF,z; while (a[x].next!=n+1) { int t=a[x].next; if (a[x].c==a[t].c) { x=a[x].next; continue; } if (abs(a[x].data-a[t].data)<y) { y=abs(a[x].data-a[t].data); z=x; } x=a[x].next; } cout<<z<<' '<<a[z].next<<'\n'; a[a[z].pre].next=a[a[z].next].next; a[a[a[z].next].next].pre=a[z].pre; } }

100分算法

双向链表可以保留。考虑如何快速找到最小的那一对。于是想到可以把每一对作为一个元素，放进优先队列里。 如果不会优先队列，可以点这里。 我是用node1把每一对打包，放入优先队列里。每次弹出队头，如果这一对中有人已出列，就跳过，不然，他们就出列。出列之后，要看一看两边新组成的这一对是不是异性，如果是，就入队。当然，双向链表还是需要的，不然找不到元素的前驱和后继。 因为优先队列内部是用堆实现的，所以每次操作的复杂度为O(logn),总复杂度为O(nlogn)。 具体实现如下。

#include<iostream> #include<cstdio> #include<queue> #include<cmath> using namespace std; int n,b[200005]; struct node { char c; int data,pre,next; } a[200005]; struct node1 { int x1,x2; node1() {} node1(int x,int y):x1(x),x2(y) {} bool operator <(node1 x) const { if (abs(a[x1].data-a[x2].data)!=abs(a[x.x1].data-a[x.x2].data)) return abs(a[x1].data-a[x2].data)>abs(a[x.x1].data-a[x.x2].data); return x1>x.x1; } }; priority_queue<node1> p; int main() { cin>>n; int g=0; for (int i=1; i<=n; i++) { cin>>a[i].c; if (a[i].c=='G') g++; } for (int i=1; i<=n; i++) { cin>>a[i].data; a[i].pre=i-1; a[i].next=i+1; } cout<<min(g,n-g)<<'\n'; for (int i=1; i<n; i++) { if (a[i].c!=a[i+1].c) { p.push(node1(i,i+1)); } } while (!p.empty()) { node1 x; x=p.top(); p.pop(); if (x.x1==0||x.x2==n+1) continue; if (b[x.x1]==1||b[x.x2]==1) continue; b[x.x1]=b[x.x2]=1; cout<<x.x1<<' '<<x.x2<<'\n'; if (a[a[x.x1].pre].c!=a[a[x.x2].next].c) p.push(node1(a[x.x1].pre,a[x.x2].next)); a[a[x.x1].pre].next=a[x.x2].next; a[a[x.x2].next].pre=a[x.x1].pre; } }

补充

关于结构体，还想再说一点。第2个程序第14行的是构造函数，可以把2个数转换为node1类型（请看第36行）。第13行本来可以不用写的，不过有了构造函数就一定要有这个函数，不然将无法定义node1类型的数（删去第13行后，第40行就写不了了）。

总结

在结构体里重载<的时候，要注意优先队列是个大根堆，若想要小的在前面，return后面就应该写>，跟它反着来。 这是我写的第一篇博客，要是有什么不足之处，望大家指出。