重题
题目描述
格格兰郡的$N$名士兵随机散落在全郡各地。
格格兰郡中的位置由一对$(x,y)$整数坐标表示。
士兵可以进行移动,每次移动,一名士兵可以向上,向下,向左或向右移动一个单位(因此,他的$x$或$y$坐标也将加$1$或减$1$)。
现在希望通过移动士兵,使得所有士兵彼此相邻的处于同一条水平线内,即所有士兵的$y$坐标相同并且 $x$坐标相邻。
请你计算满足要求的情况下,所有士兵的总移动次数最少是多少。
需注意,两个或多个士兵不能占据同一个位置。
输入格式
第一行输入整数$N$,代表士兵的数量。
接下来的$N$行,每行输入两个整数$x$和$y$,分别代表一个士兵所在位置的$x$ 坐标和$y$坐标,第$i$行即为第$i$个士兵的坐标$(x[i],y[i])$。
输出格式
输出一个整数,代表所有士兵的总移动次数的最小值。
数据范围
$1\leq N\leq 10000$
$−10000\leq x[i],y[i]\leq 10000$
输入样例
5
1 2
2 2
1 3
3 -2
3 3
输出样例
8
算法1 (排序+中位数) $O(nlog_n)$
建议做前置题:货仓选址
这边有题解->题解(没错还是我写的)
易发现,$X$和$Y$中间是没有关联的,所以可以分开讨论。
$Y$的坐标讨论:
首先发现士兵最终的$Y$坐标都是相等的,所以可把它们压缩在一个平面。这一小块就变成货仓选址了(题解放在上面了),这里就不详细说了
$X$的坐标讨论:
士兵的最终$X$坐标显然是不一样的,怎么办呢?很简单,只要把他们的$X$统一就行了,把$x_i$每个都减$i$(这个操作的前面要排序,才可使答案最小)。又变成货仓选址了(题解放在上面了),这里就不详细说了
大致思路
先把$x[]$和$y[]$都排一下序
sort(x+1,x+n+1);
sort(y+1,y+n+1);
$x$再做一次处理
for(i=1;i<=n;i++) x[i]-=i;
sort(x+1,x+n+1);
中位数求答案
mid_x=x[n/2];
mid_y=y[n/2];
for(i=1;i<=(n+1);i++) ans+=abs(x[i]-mid_x);
for(i=1;i<=(n+1);i++) ans+=abs(y[i]-mid_y);
举个例子
例子:
5
1 2
2 2
1 3
3 -2
3 3
先把$x[]$和$y[]$都排一下序:
x:1 1 2 3 3
y:-2 2 2 2 3
x再做一次处理:
x:-2 -1 -1 -1 0
y:-2 2 2 3 3
中位数求答案:
$|-1-(-2)|+|-1-(-1)|+|-1-(-1)|+|-1-(-1)|+|-1-0|+|2-(-2)|+|2-2|+|2-2|+|2-3|+|2-3|$
时间复杂度$O(nlogn)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,i,x[10086],y[10086],mid_x,mid_y,ans;
int main()
{
cin>>n;
for(i=1;i<=n;i++) cin>>x[i]>>y[i];
sort(x+1,x+n+1);
sort(y+1,y+n+1);
for(i=1;i<=n;i++) x[i]-=i;
sort(x+1,x+n+1);
mid_x=x[(n+1)/2];
mid_y=y[(n+1)/2];
for(i=1;i<=n;i++) ans+=abs(x[i]-mid_x);
for(i=1;i<=n;i++) ans+=abs(y[i]-mid_y);
cout<<ans;
return 0;
}
不懂
x[] - i
之后又变成货仓选址问题,很难理解,求解释QAQ众所周知,货舱选址问题是要求选择一个位置 $pos$,最小化 $\sum\limits_{i=1}^{n}\vert x_i-x\vert $,而本题是选择最左边的位置 $pos$,要求最小化 $\sum_{i=1}^n\vert x_i-x-i\vert$,把 $x_i$ 减去 $i$ 即可
xi - i
数组的货仓选址 %%%草,重题了/fn