题解：P10461 Soldiers

思路

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

为什么可以呢？

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

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

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

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

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

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

$$ \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;
}