Luogu P1878 事实上这道题并不难，但我真没弄懂我手写堆为什么过不了。所以
STL大法好！！！
基本思路
对于每一对相邻异性，将他们的舞蹈技术的差插入一个堆 通过维护这个小根堆，每次就可以取得舞蹈技术差最小的一对 值得注意的是，每次取完一对舞伴之后，要对这对舞伴进行标记，并将堆中所有有这两位舞者参与的舞伴弹出这个堆。并且还需要找到这一对舞伴两边的第一个未被挑出的人，如果是异性则可以作为新的舞伴加入堆
代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std
;
struct data
{
int l
,r
,val
;
bool operator <(const data
&x
) const
{
if (x
.val
!=val
) return x
.val
<val
;
else return x
.l
<l
;
}
};
int len
,n
,que
[200005],a
[200005],ans
,group1
[200005],group2
[200005],rlen
;
bool choice
[200005];
priority_queue
<data
> heap
;
int main()
{
scanf("%d\n",&n
);
for (int i
=1;i
<=n
;i
++)
{
char c
;
scanf("%c",&c
);
if (c
=='B') que
[i
]=true;
}
scanf("%d",&a
[1]);
for (int i
=2;i
<=n
;i
++)
{
scanf("%d",&a
[i
]);
if (que
[i
]!=que
[i
-1])
{
data rec
;
rec
.l
=i
-1;rec
.r
=i
;
rec
.val
=abs(a
[i
]-a
[i
-1]);
heap
.push(rec
);
}
}
while (!heap
.empty())
{
data rec
=heap
.top();
ans
++;
group1
[ans
]=rec
.l
;
group2
[ans
]=rec
.r
;
choice
[rec
.l
]=choice
[rec
.r
]=true;
while (choice
[rec
.l
]||choice
[rec
.r
])
{
if (heap
.empty()) break;
heap
.pop();
rec
=heap
.top();
}
int l
=group1
[ans
];int r
=group2
[ans
];
while (l
>0&&choice
[l
]) l
--;
while (r
<=n
&&choice
[r
]) r
++;
if (que
[l
]!=que
[r
]&&l
>0&&r
<=n
)
{
rec
.l
=l
;
rec
.r
=r
;
rec
.val
=abs(a
[l
]-a
[r
]);
heap
.push(rec
);
}
}
printf("%d\n",ans
);
for (int i
=1;i
<=ans
;i
++) printf("%d %d\n",group1
[i
],group2
[i
]);
return 0;
}
