AcWing-123-士兵

2021-03-04 · 165次阅读 · 原创 · 数据结构与算法

#题解 #算法竞赛 #排序

问题

格格兰郡的 N 名士兵随机散落在全郡各地。

格格兰郡中的位置由一对 (x,y) 整数坐标表示。

士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的 x 或 y 坐标也将加 1 或减 1）。

现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的 y 坐标相同并且 x 坐标相邻。

请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。

需注意，两个或多个士兵不能占据同一个位置。

输入格式

第一行输入整数 N，代表士兵的数量。

接下来的 N 行，每行输入两个整数 x 和 y，分别代表一个士兵所在位置的 x 坐标和 y 坐标，第 i 行即为第 i 个士兵的坐标 (x[i],y[i])。

输出格式

输出一个整数，代表所有士兵的总移动次数的最小值。

数据范围

1≤N≤10000,
−10000≤x[i],y[i]≤10000

输入样例：

输出样例：

思路

排序＋货仓选址。

由题意，其最终答案可以拆解为两个部分：

所有士兵垂直移动的距离之和
所有士兵水平移动的距离之和

对于１，其最终的士兵都在同一条直线上，则 y 轴相同，所以说有的士兵都会移动到同一 y 坐标上，即为：找一个点，使得士兵的y轴坐标到该点的距离的绝对值之和最小（即货仓选址问题）。

对于２，士兵可能是离散分开的点，而最终排为一行连续的点，其相对的在x轴上的前后位置不会发生改变，其坐原标为 $x_0,x_1,x_2,...,x_{n-1}$ （ $x_i$ 不一定连续），最后的坐标为 $a,a+1,a+2,a+3,...,a+n-1$ （是连续的坐标），则所有士兵移动的距离之和为 $\sum_{i=0}^{n-1}[x_i-(a+i)]=>\sum_{i=0}^{n-1}[(x_i-i)-a]$ ，从该式子也可看出其为货仓选址问题。

题解

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int MAX = 1e4 + 10;
int n;
int y[MAX], x[MAX];

//货仓选址问题模板
int work(int *a) {
    sort(a, a + n);
    int mid = a[n / 2], res = 0;
    for (int i = 0; i < n; ++i) {
        res += abs(a[i] - mid);
    }
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &x[i], &y[i]);
    }

    sort(x, x + n); //需要先排序
    for (int i = 0; i < n; ++i) {
        x[i] -= i;
    }

    cout << work(y) + work(x) << endl;

    return 0;
}

标题：	AcWing-123-士兵
链接：	https://www.fightingok.cn/detail/63
更新：	2022-09-18 22:35:41
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可