SOLDIERS(中位数）

这道题是对一维中位数定理的一个延伸，变成了二维的形式，其实本质是一样的，只不过要多操作几步。

对于本道题，要确定一个最短长度，那么首先要确定在哪一行，即纵坐标是多少。

因此这就变成了求中位数的情况，那么先对所有的纵坐标进行排序，排序完成之后确定纵坐标的中点，然后遍历所有坐标，将其与中点坐标的纵坐标相减取绝对值，那么y方向上的距离就求好了，并且是y方向上的最短距离。

对于横坐标刚开始没看到要相连。。。对于求横坐标的最短距离，由于是相连的，那么假设第一个相连的横坐标是k，那么接下来的n-1个点的横坐标分别是k+1, k + 2 ... , k + n - 1, 并且设当前最左边的一个士兵的横坐标为X₀，那么横坐标的最短距离就是 S = |K-X₀| + |K + 1 - X₁| + |K + 2 - X₂| + ... + |K + N - 1 - (X_N_{- 1}) |,而K则是横坐标的中点。

那么这就很清楚了，代码如下：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 const int N = 10010;
 7 
 8 int a[N], b[N];
 9 
10 int main(){
11     int n, cnt = 0;
12     cin >> n;
13     for(int i = 0; i < n; i ++)
14         cin >> a[i] >> b[i];
15     sort(b, b + n);
16     sort(a, a + n);
17     int mid = n / 2;
18     for(int i = 0; i < n; i ++){
19         a[i] -= i;
20         cnt += abs(b[mid] - b[i]);
21     }
22     sort(a, a + n);
23     for(int i = 0; i < n; i ++)
24         cnt += abs(a[mid] - a[i]);
25     cout << cnt << endl;
26 
27     return 0;
28 }