自动搬运

查看原文

来自洛谷，原作者为

	NIMNIM 我超甜

搬运于2025-08-24 21:31:24，当前版本为作者最后更新于2019-10-27 18:22:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题

是暑假的时候教练给我们测试的一道题，说实话，当时没打完，究其原因，竟是我代码能力太差了思路太复杂了qwq

但是，尽管思路比较清奇，我也觉得可能会有和我想的一样但是代码打不出来的人，所以我要发一发题解来帮帮大伙

题解里面有打上标记的，而可以说用的不是 $bool$ 类型的标记而是 $int$ 类型的标记

我们大部分人自然都知道优先队列（大根/小根堆），这里不再赘述，就给个链接

下面进入问答环节：

$ASK:$ 这道题怎么用优先队列？？？

$ANSWER:$ 其实想想也不难，只要用优先队列来维护相邻舞者之间的技术值的差，每次取最小的就OK了

$ASK:$ 有一对跳了之后，TA们两边的怎么办？

$ANSWER:$ 这个问题其实也不算难，我们只要用链表结构，断链重连，放入队列就好了

问答环节结束

看到这儿，可能你就跑去打代码了对吧，但是，停下！！！ （当然你真的会了你自然可以走了我不留你

但是还有一个比较重要的问题：

对于一排舞者，B1 G1 B2 G2 ，我们一开始存储并放入队列的是什么，是每两个相邻的舞者的差，那假设 G1 B2 先出来，然后断链重连，那么B1 G1 的联系以及 B2 G2 的联系该怎么办？？？

这时候，我们就要学会打标记了。

我们有两种可选的思路：

第一种比较简单，即在每一对舞者出列之后对这两个舞者都打上标记，以后在优先队列中取出TA们的时候不执行操作就是了

第二种则有点蠢难，就是在每次更新差值的时候，用int数组存放更新了的差值，如果在后面从优先队列中取出的差值与之前存放的差值不相等的话，则说明这个差值未被更新的，那也不执行操作即可

（第二种是我这种菜鸡用的方法，看不太懂就学第一个吧）

代码来了：

1.第一种的之前题解似乎有

2.第二种：

#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;
}

写了好久。。。求管理大大通过；求读者赞赞。