ACWing 123 士兵

题目大意

给定\(n\)个点\((x_i,y_i)\)，要求最少的移动次数，将\(n\)个点的\(y_i\)相等，\(x_i\)相邻，即形成一条平行于\(y\)轴的直线。\(n \le 10000\)

简单口胡

首先需要确定这些点在哪条直线上。
设这条直线为\(y = k\)，那么即要最小化\(\sum {|y_i - k|}\)，那么没了，\(k = M(y)\)，\(M(y)\)即为\(y\)的中位数。

将点移到最后的答案位置，相对位置不变，即若\(x_i < x_j\)，那么移过去后的\(x‘_i,x‘_j\)也满足\(x‘_i < x‘_j\)

那么先按\(x\)排序，假设点集为\(a,a+1,a+2,\cdots,a + n - 1\)，那么对于第\(i\)个点，距离为\(|x_i - (a + i - 1)| = |x_i - (i - 1) - a|\)，最小化\(\sum {x_i - (i - 1) - a}\)，那么没了，\(a = M(x - (i - 1))\)

# include <bits/stdc++.h>
using namespace std;
int n;
int x[10005],y[10005];

int cnt = 0;

int main(void)
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    sort(x + 1, x + n + 1); // to find where
    sort(y + 1, y + n + 1);
    int midy = y[(n + 1) >> 1];
    for(int i = 1; i <= n; i++) cnt += abs(y[i] - midy);
    for(int i = 1; i <= n; i++) 
    {
        x[i] -= (i - 1);
    }
    sort(x + 1,x + n + 1);
    int midx = x[(n + 1) >> 1];
    for(int i = 1; i <= n; i++) cnt += abs(x[i] - midx);
    printf("%d\n",cnt);
    return 0;
}

ACWing 123 士兵

原文：https://www.cnblogs.com/luyiming123blog/p/14218667.html