题目链接

题意分析

由于题目要求没有说一块特定的石头上必须要到一个特定的位置

而是要求每一个位置上有石头就行

所以我们把石头的原始位置与目标位置排序 这样也保证了石头之间的移动轨迹互不交叉

存在方案 必须满足如下两个条件

1.石头向左移动的总距离和向右移动的总距离必须相等

2.我们从左往右扫的时候 必须时刻满足石头向右移动的总距离≥向左移动的总距离

从第二个条件 我们可以发现 这跟括号匹配的模型很像

如果均满足的话 我们使用栈 用类似于括号匹配的方式 得到每一次的操作 具体见代码‘

CODE:

#include

#define N 300080
#define M 1580000
using namespace std;
int n,tot,top;
struct Node
{
	int pos,id;
	friend bool operator <(const Node &A,const Node &B)
	{return A.posnum[i].pos) sta[++top]=i;
		else
		{
			while(top>0)
			{
				int tmp=min(aim[sta[top]].pos-num[sta[top]].pos,num[i].pos-aim[i].pos);
				num[sta[top]].pos+=tmp;
				num[i].pos-=tmp;
				ans[++tot]=(ANS){num[sta[top]].id,num[i].id,tmp};
				if(num[sta[top]].pos==aim[sta[top]].pos) top--;
				if(num[i].pos==aim[i].pos) break;
			}
		}
	}
	printf("%d\n",tot);
	for(int i=1;i<=tot;++i)
	printf("%d %d %d\n",ans[i].le,ans[i].ri,ans[i].d);
	return 0;
}