题意大概是介样的：
n个士兵的位置坐标随机分布在全国各地。
坐标由一对（x，y）给出（x，y均为整数）。士兵可以从一个格子移动到另一个格子，方向可以为向上、向下、向左或向右移动一个单位（换言之，他可以将x或y坐标加1或减1）。现在士兵们想进入同一条水平线，且彼此相邻（即他们的最终位置是（x，y），（x + 1，y），……，（x + n - 1，y））。水平线上士兵的最终顺序是任意的。
目标是尽量减少所有士兵进入这种状态的移动总数。
两个或两个以上的士兵不得同时占据同一位置。
输出移动总数的最小值。
对于y，排序后取中位数即为y的最终值。
对于x则要复杂一些，因为最后x并不是移动到同一个点，而是彼此相邻排列，不妨假设排好之后的起始位置的再左边一格为A，->表示移动，即：
x[1] -> A + 1；
x[2] -> A + 2；
x[3] -> A + 3；
……
x[n] -> A + n.
换言之：
x[1] - 1 -> A；
x[2] - 2 -> A；
x[3] - 3 -> A；
……
x[n] - n -> A.
即：
x_new[i] = x[i] - i；
再取中位数即为x的最终值了。
代码实现如下：
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (register int i = a; i <= b; i++) const int maxn = 1e4 + 5; int n, ans = 0, mid_x, mid_y; int x[maxn], y[maxn]; int ABS(int a, int b) {return a > b ? a - b : b - a;} int read() { int x = 0, flag = 0; char ch = ‘ ‘; while (ch != ‘-‘ && (ch < ‘0‘ || ch > ‘9‘)) ch = getchar(); if (ch == ‘-‘) { flag = 1; ch = getchar(); } while (ch >= ‘0‘ && ch <= ‘9‘) { x = (x << 1) + (x << 3) + ch - ‘0‘; ch = getchar(); } return flag ? -x : x; } void write(int x) { if (x < 0) { putchar(‘-‘); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + ‘0‘); } int main() { n = read(); rep(i, 1, n) x[i] = read(), y[i] = read(); sort(x + 1, x + n + 1); sort(y + 1, y + n + 1); rep(i, 1, n) x[i] -= i; sort(x + 1, x + n + 1); if (n & 1) { mid_x = x[(n + 1) >> 1]; mid_y = y[(n + 1) >> 1]; } else { mid_x = x[n >> 1]; mid_y = y[n >> 1]; } rep(i, 1, n) ans += ABS(x[i], mid_x) + ABS(y[i], mid_y); write(ans); return 0; }
原文：https://www.cnblogs.com/Kirisame-Marisa/p/10847723.html
