题解 P1878 【舞蹈课】
NIMNIM
·
·
题解
这道题
是暑假的时候教练给我们测试的一道题，说实话，当时没打完，究其原因，竟是我代码能力太差了思路太复杂了qwq
但是，尽管思路比较清奇，我也觉得可能会有和我想的一样但是代码打不出来的人，所以我要发一发题解来帮帮大伙
题解里面有打上标记的，而可以说用的不是 bool 类型的标记而是 int 类型的标记
我们大部分人自然都知道优先队列（大根/小根堆），这里不再赘述，就给个链接
下面进入问答环节：
$ANSWER:$ 其实想想也不难，只要用优先队列来维护相邻舞者之间的技术值的差，每次取最小的就OK了
$ASK:$ 有一对跳了之后，TA们两边的怎么办？
$ANSWER:$ 这个问题其实也不算难，我们只要用链表结构，断链重连，放入队列就好了
~~问答环节结束~~
------------
看到这儿，可能你就跑去打代码了对吧，但是，停下！！！ ~~（当然你真的会了你自然可以走了我不留你~~
但是还有一个比较重要的问题：
对于一排舞者，B1 G1 B2 G2 ，我们一开始存储并放入队列的是什么，是每两个相邻的舞者的差，那假设 G1 B2 先出来，然后断链重连，那么B1 G1 的联系以及 B2 G2 的联系该怎么办？？？
这时候，我们就要学会打标记了。
------------
### 我们有两种可选的思路：
**第一种**比较简单，即在每一对舞者出列之后对这两个舞者都打上标记，以后在优先队列中取出TA们的时候不执行操作就是了
**第二种**则有点~~蠢~~难，就是在每次更新差值的时候，用int数组存放更新了的差值，如果在后面从优先队列中取出的差值与之前存放的差值不相等的话，则说明这个差值未被更新的，那也不执行操作即可
~~（第二种是我这种菜鸡用的方法，看不太懂就学第一个吧）~~
------------
#### 代码来了：
1.第一种的之前题解似乎有
2.第二种：
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define inf 2000000000
int ans[200005][2],sum=0;
struct node//链表
{
int l,r,cha,xu;
bool judge;
}a[200005];
bool operator<(node rr,node ll)//优先队列有限法则
{
int lll=abs(ll.cha),rrr=abs(rr.cha);
if(rrr!=lll)
return lll<rrr;
else
return ll.xu<rr.xu;
}
priority_queue <node> que;
int main ( )
{
//freopen("dance.in","r",stdin);
//freopen("dance.out","w",stdout);
int n,now,next,t=0;
char x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>x;
if(x=='B') a[i].judge=0;
else a[i].judge=1;
} //以上性别判断
scanf("%d",&now);
for(int i=1;i<n;i++)
{
scanf("%d",&next);
a[i].xu=i; //自身是第几个
a[i].cha=next-now;//预处理技术值差
a[i].l=i-1;a[i].r=i+1;//预处理左右
que.push(a[i]);
now=next;
}
a[n].r=n+1;a[n].xu=n;a[n].cha=inf;
while(!que.empty())//开始模拟过程
{
int xx=que.top().xu,cmp=que.top().cha;
que.pop();
int yy=a[xx].r;
if(a[xx].cha==cmp/*判断是否是更新过的*/&&a[xx].judge!=a[yy].judge/*一男一女*/
&&xx!=0&&yy!=n+1/*特判链表首尾 */)
{
ans[++t][0]=xx;ans[t][1]=yy;
a[a[xx].l].cha+=a[xx].cha+a[yy].cha;//更新差值
a[a[yy].r].l=a[xx].l;a[a[xx].l].r=a[yy].r;//断链重连
if(a[xx].l>0&&a[yy].r<=n)//特判链表首尾
que.push(a[a[xx].l]);//入队列
a[xx].l=a[xx].r=0;a[yy].l=a[yy].r=n+1;
}
}
printf("%d\n",t);
for(int i=1;i<=t;i++)
printf("%d %d\n",ans[i][0],ans[i][1]);
return 0;
}
```
写了好久。。。求管理大大通过；求读者赞赞。