自动搬运

查看原文

来自洛谷，原作者为

	JK_LOVER 却顾所来径，苍苍横翠微。

搬运于2025-08-24 22:19:37，当前版本为作者最后更新于2020-05-27 16:41:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目描述

在 $n \times n$ 的网格中，使每一排，每一列都只有一个棋子，求方案步数的最小值。

分析

我们发现每一排，每一列是不影响的，那么可以考虑先按 $x$ 轴排序，再按 $y$ 轴排序，贪心的选取第 $i$ 个。证明：

$$\text{有以下原坐标排序:} \ a_1\le a_2 \le a_3 \le ...\le a_n $$$$ans_1= \sum_i^n abs(a_i-i)$$

$\text{若交换第x,y个(x < y):}$

$$ans_2 = \sum_{i,i \neq x,y}^nabs(a_i-i)+abs(a_x-y)+abs(a_y-x) $$$$abs(a_x-x)+ abs(a_y-y) \le abs(a_x-y)+ abs(a_y-x)$$

因为点 $(a_x,a_y)$ 一定在直线 $y=x$ 之上，所以 $(x,y)$ 的曼哈顿距离一定比 $(y,x)$ 更短

所以由小到大一定最优。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5110;
struct node
{
    int x,y,id; 
}s[N];
struct Q{
	int id,M;
	char A;
}st[N];
inline int read()
{
    int t=0,f = 0;char a=getchar();
	while(a<'0'||a>'9'){if(a=='-')f=1;a=getchar();}
    while(a>='0'&&a<='9'){t=(t<<1)+(t<<3)+a-'0';a=getchar();}
	return f?-t:t;
}
bool cmp1(node a,node b)
{
	return a.x<b.x;
}
bool cmp2(node a,node b)
{
	return a.y<b.y;
}
long long n,ans = 0,top = 0;
int main()
{
	n = read();
	for(int i = 1;i <= n;i++)
	s[i].x = read(),s[i].y = read(),s[i].id = i;
	sort(s+1,s+1+n,cmp1);
	for(int i = 1;i <= n;i++)
	{
		int f = s[i].x - i;
		ans += abs(f);
		if(f < 0)
		{
			st[++top].id = s[i].id;
			st[top].M = abs(f);
			st[top].A = 'D';
		}
		if(f > 0)
		{
			st[++top].id = s[i].id;
			st[top].M = abs(f);
			st[top].A = 'U';
		}
	}
	sort(s+1,s+1+n,cmp2);
	for(int i = 1;i <= n;i++)
	{
		int f = s[i].y - i;
		ans += abs(f);
		if(f < 0)
		{
			st[++top].id = s[i].id;
			st[top].M = abs(f);
			st[top].A = 'R';
		}
		if(f > 0)
		{
			st[++top].id = s[i].id;
			st[top].M = abs(f);
			st[top].A = 'L';
		}
	}
	printf("%lld\n",ans);
	for(int i = 1;i <= top;i++)
	{
		for(int j = 1;j <= st[i].M;j++)
		{
			printf("%d %c\n",st[i].id,st[i].A);
		}
	}
}

博客地址