题解：P10461 Soldiers

思路

将本题中的士兵横纵坐标分开考虑。

为什么可以呢？

考虑士兵不能同时占据同一位置，那就让其中一个先走，另一个后走即可。其中由于最开始不会有两个或更多的士兵同时占据同一位置，所以结论显然正确。然后所有人统一先动 x 或先动 y 就可以将 x 和 y 分开考虑了。

因为他们最后都是要 $y$ 坐标相同的，所以我们设士兵要移动到的目标纵坐标为 $y_0$。

所以，士兵在垂直于 x 轴方向上的移动距离为：

$$\sum_{i = 1}^{n}{|y_i-y_0|}$$

那么 $y_0$ 取什么值最小呢？就是 $y$ 序列的中位数。

接下来我们设最终序列的第一位士兵 $x$ 为 $x_0$，则最终花费为：

$$\sum_{i=1}^n |x_i-(k+i)|$$

变形为：

$$\sum_{i=1}^n |(x_i-i)-k|$$

就又是中位数了。

代码

#include<bits/stdc++.h>
using namespace std;
int x[10000+10],y[10000+10],n,ans;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	sort(&x[1],&x[n+1]); sort(&y[1],&y[n+1]);
	for(int i=1;i<=n;i++) x[i]-=i; sort(&x[1],&x[n+1]);
	for(int i=1;i<=n/2;i++) ans+=x[n-i+1]-x[i]+y[n-i+1]-y[i];
	cout<<ans<<endl;
	return 0;
}