题解

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int M = 10005;
int x[M], y[M], tx[M]; // x/y：存储士兵原始坐标；tx：存储x坐标变换后的值

int main() {
	
	// 1. 问题拆分：二维移动拆分为x、y两个独立一维问题，分别算最小步数再求和
	// 2. y轴：所有士兵需站同一y值，选y的中位数（最小化绝对差之和）
	// 3. x轴：士兵需站连续x值(a,a+1,...,a+n-1)，先排序x，再变换x'=x-i，选x'的中位数
	
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
	}
	
	// ========== 第一步：计算y轴（垂直方向）最小步数 ==========
	// 排序y坐标：为找中位数做准备
	sort(y, y + n);
	// 取y坐标的中位数：无论n是奇数/偶数，n/2位置的数是最优选择（最小化绝对差之和）
	int y_med = y[n / 2];
	// 累计y轴总步数：用long long避免极端情况（如n=1e4，步数和超大）溢出
	long long y_sum = 0;
	for (int i = 0; i < n; ++i) {
		// 每个士兵y坐标到中位数的绝对距离 = 垂直移动步数
		y_sum += abs(y[i] - y_med);
	}
	
	// ========== 第二步：计算x轴（水平方向）最小步数 ==========
	// 排序原始x坐标：让士兵按x坐标有序，对应后续“连续位置”的顺序
	sort(x, x + n);
	// 坐标变换：x'_i = x_i - i
	// 原理：最终第i个士兵要站在a+i（连续位置），步数=|x_i - (a+i)|=|(x_i-i)-a|
	// 变换后只需让所有x'_i移动到同一值a（中位数），即可满足连续位置要求
	for (int i = 0; i < n; ++i) {
		tx[i] = x[i] - i;
	}
	// 排序变换后的x'：为找中位数做准备
	sort(tx, tx + n);
	// 取变换后x'的中位数
	int x_med = tx[n / 2];
	// 累计x轴总步数
	long long x_sum = 0;
	for (int i = 0; i < n; ++i) {
		// 每个变换后x'到中位数的绝对距离 = 水平移动步数
		x_sum += abs(tx[i] - x_med);
	}
	
	// 总步数 = 垂直步数 + 水平步数
	cout << y_sum + x_sum << endl;
	return 0;
}