中位数

每一个士兵的横纵坐标互不影响，可以分开处理，对于纵坐标，求最小的移动次数，那么目标坐标一定是他们的中位数，对于横坐标，由于不能重合，实际上就是在数轴上找到一个点a使得，|x1 - a| + |x2 - (a + 1)| + … + |xn - (a + n - 1)|最小，对一个新的数组求中位数即可

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10005;
int x[N];
int y[N];

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];

    sort(x, x + n);
    sort(y, y + n);

    int a, b;
    b = y[n / 2];

    long long res = 0;
    for(int i = 0; i < n; i++) res += abs(y[i] - b);
    for(int i = 0; i < n; i++) x[i] -= i + 1;

    sort(x, x + n);
    a = x[n / 2];

    for(int i = 0; i < n; i++) res += abs(x[i] - a);

    cout << res << endl;

    return 0;
}