P1889 士兵站队 题解

yydfj · 2021-03-13 10:09:19 · 题解

问题简述

这道题我们可以换另一种思路去看待它，就容易理解了：

在一个平面上，把 n 个点排列在一条与 x 轴平行的直线的整点上，且相邻两点的距离为 1 。

求一种排列方案，使得这 n 个点到目标位置的曼哈顿距离和最小。

解法综述

由于是求曼哈顿距离，所以可以将 x , y 分开考虑。

• 可以通过微量法证明 $y_0$ 一定在某个已知 $y_i$ 上。再通过微量法证明 $y_0$ 一定是 $y_i$ 的中位数。
• 先将 $x$ 排序，可以证明 $x$ 的顺序一定就是最终的序列的顺序（因为交叉位置的话解更差）。 因为定了序，所以有 $x_i=x_0+i-1$ ，则可以将问题转化为 $x_i=x_i-(i-1)=x_i-i+1=x_0$ 。 $x$ 就是与 $y$ 同样的问题了，求 $x_i-i+1$ 的中位数 $x_0$ 就可以了。

综上述可知，这道题其实是一道贪心题。

代码描述

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
int n,x[10001],y[10001],ans;
void xsort(int l,int r)//用于将x轴上的士兵进行排序
{
    int i=l,j=r,m=x[(l+r)/2];
    while(i<=j)
    {
        while(x[i]<m) i++;
        while(x[j]>m) j--;
        if(i<=j)
        {
            swap(x[i],x[j]);
            i++;j--;
        }
    }
    if(l<j) xsort(l,j);
    if(i<r) xsort(i,r);
}
void ysort(int l,int r)//用于将y轴上的士兵进行排序
{
    int i=l,j=r,m=y[(l+r)/2];
    while(i<=j)
    {
        while(y[i]<m) i++;
        while(y[j]>m) j--;
        if(i<=j)
        {
            swap(y[i],y[j]);
            i++;j--;
        }
    }
    if(l<j) ysort(l,j);
    if(i<r) ysort(i,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);//输入当前士兵的坐标
    xsort(1,n);
    ysort(1,n);//将士兵的坐标进行排序
    for(int i=1;i<=n;i++) ans+=abs(y[i]-y[(n+1)/2]);//累加排序后士兵y坐标离y0的距离
    for(int i=1;i<=n;i++) x[i]=x[i]-i+1;
    xsort(1,n);//处理完士兵x坐标后需要再次排序
    for(int i=1;i<=n;i++) ans+=abs(x[i]-x[(n+1)/2]);//累加排序后士兵x坐标离x0的距离
    printf("%d",ans);//输出答案（为曼哈顿距离和最小）
    return 0;
}

这是本蒟蒻第一次写的题解，如有错误点请好心指出！

该题解审核通过后有人指出错误，已被修改 1 次。