自动搬运

查看原文

来自洛谷，原作者为

	xiejinhao 人间总有一两风，填我十万八千梦

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

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

以下是正文

P1889 士兵站队 题解

好多Dalao写的我没看明白，那么我就自己写一篇吧

附送题目链接：P1889士兵站队

那么我就不多解释题目了；

对于输入士兵的坐标：

纵坐标处理

我们先看纵坐标（其实是纵坐标比较简单）

• 我们假设士兵要移动到的目标纵坐标为m；

那么我们可以推导出一大堆的东西： 士兵在垂直于x轴方向上的移动距离为：

	|y1-m|+|y2-m|+|y3-m|+……+|yn-1-m|+|yn-m|

那么m取什么值最小呢？显而易见，就是y1~yn序列的中位数，实现代码如下：

	int rey;
   	sort(y+1,y+n+1);
	if(!n%2) rey=(y[n/2]+y[n/2+1])/2;
	//!n%2意为 n%2 =0(在if语句里写2个'=')，即 n%2 为假
	else rey=y[n/2+1];
		

横坐标处理

现在到了x麻烦了，因为有可能两位士兵的横坐标是相同的！而纵坐标的相同对于计算并没有影响！

~到这里实在不懂的要自己画下图了~

那接着怎么办？

• 依旧假设~ ，我们假设第一位士兵站的位置是k，因为x从x1开始，那么我们假设成起始位置为k+1吧(不懂接着看完你就懂了）

那么：第二位士兵的位置是 k+2，接着是k+3,k+4,……,k+n;

所以，士兵横向(即平行于y轴方向)移动的距离为：

	|x1-(k+1)|+|x2-(k+2)|+|x3-(k+3)|+……+|x(n-1)-(k+n-1)|+|xn-(k+n)|

那么k取何值会使上式最小？我们不妨变形一下：

	|(x1-1)-k)|+|(x2-2)-k)|+|(x3-3)-k)|+……+|(x(n-1)-(n-1))-k)|+|(xn-n)-k)|
 //x(n-1)中 n-1 是x的下标

emmmm……于是又是中位数了！

结论：我们只需要取 k=xi-i的中位数就好了！

代码很容易实现，同纵坐标的的处理，先排序，但这次我们要将xi-i之后再次排序，再取中位数；

代码实现如下：

	int rex;
	sort(x+1,x+n+1);
	for(int i=1;i<=n;i++) x[i]-=i;
	sort(x+1,x+n+1);
  	//处理完还要再排序；
	if(!n%2) rex=(x[n/2]+x[n/2+1])/2;
   	//同上；
	else rex=x[n/2+1];

到此，核心的部分就结束了

然后程序就over了；

完整代码实现：

//认真看 杜绝抄袭 
#include<cstdio>
#include<algorithm>
//使用 sort 排序函数 调用算法库; 
#include<cmath>
//使用 abs 绝对值函数 调用数学库;
using namespace std;
int n,x[10005],y[10005],ans=0,rex,rey;
//输入士兵数n，x数组储存士兵横坐标，y数组储存士兵纵坐标;
//ans统计步数和，rex记平行于x轴(即横方向)的中位数，rey记行于y轴(即纵方向)的中位数; 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",x+i,y+i);
	//输入完毕 
	sort(x+1,x+n+1); sort(y+1,y+n+1);
	//无论如何都要先排序,sort调用'algorithm'(算法)库; 
	for(int i=1;i<=n;i++) x[i]-=i;
	sort(x+1,x+n+1);
	//处理完横坐标还要再排序一次; 
	if(!n%2)
	//人数n为偶数; 
	//相当于'if(n%2==0)'; 
	{
		rex=(x[n/2]+x[n/2+1])/2;
		rey=(y[n/2]+y[n/2+1])/2;
		//数学知识不解释了，自己多算; 
	}
	else//否则为奇数 
	{
		rex=x[n/2+1];
		rey=y[n/2+1];
	}
	for(int i=1;i<=n;i++) ans+=abs(x[i]-rex)+abs(y[i]-rey);
	//abs为绝对值函数，调用'cmath'(数学)库; 
	printf("%d",ans);
	//输出完毕,程序结束; 
	return 0;//这个千万不能漏！ 
} 

看都看完了，点个赞如何？