# [FZOJ1537]&&[2014.9.13 模拟赛] 舞蹈课 (dancingLessons)

4
BGBG
4 2 4 3

2
3 4
1 2

FZOJ 1537

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct dancer
{
int idx,idy,dif;
bool operator > (const dancer &temp) const
{
if (dif!=temp.dif) return dif>temp.dif;
else if (idx!=temp.idx) return idx>temp.idx;
else if (idy!=temp.idy) return idy>temp.idy;
}
};
{
int x,y;
}ans[200005];
bool used[200005];
int a[200005],pre[200005],nxt[200005];
char c[200005];
priority_queue < dancer , vector<dancer> , greater<dancer> > q;
int sum,tx,ty;
dancer tmp;
int main()
{
scanf("%s",c+1);
for (i=1;i<=n;i++)
{
if (i>1 && c[i]!=c[i-1]) q.push((dancer){i-1,i,abs(a[i]-a[i-1])});
}
for (i=1;i<=n;i++) pre[i]=i-1,nxt[i]=i+1;
memset(used,false,sizeof(used));
memset(ans,0,sizeof(ans));
sum=0;
while (!q.empty())
{
tmp=q.top();q.pop();
if (!used[tmp.idx] && !used[tmp.idy])
{
used[tmp.idx]=used[tmp.idy]=true;
nxt[pre[tmp.idx]]=nxt[tmp.idy];
pre[nxt[tmp.idy]]=pre[tmp.idx];
ans[++sum].x=tmp.idx;
ans[sum].y=tmp.idy;
}
tx=pre[tmp.idx];ty=nxt[tmp.idy];
if (tx>0 && ty<=n && c[tx]!=c[ty] && !used[tx] && !used[ty]) q.push((dancer){tx,ty,abs(a[tx]-a[ty])});
}
printf("%d\n",sum);
for (i=1;i<=sum;i++) printf("%d %d\n",ans[i].x,ans[i].y);
return 0;
}``````