| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 6393 | Accepted: 2421 |
Description
Input
Output
Sample Input
5 1 2 2 2 1 3 3 -2 3 3
Sample Output
8
题目：
有N个士兵，每个士兵站的位置用一个坐标（x，y）表示，现在要将N个士兵站在同一个水平线，即所有士兵的y坐标相同并且x坐标相邻，每个士兵每次可以移动一个位置。求出最少的移动步数。
解题思路：
（借鉴了网上其他人的思路）
x方向和y方向分开讨论。
1 y方向：
要使士兵最后位于同一水平线，则最终所有士兵的y坐标相同。
将所有坐标的y值从小到大排序，对于首尾两个y值，移动到它们之间的任何y值所需要的步数是相同的，所以 最终的y值取中位数。
y方向的步数y_steps=|y[0]-y_mid|+|y[1]-y_mid|+...+|y[n-1]-y_mid|，y_mid=y[n/2]。
2 x方向：
x方向稍微复杂点，先对所有x坐标从小到大排序，由于要移动步数最少，所以最终的x坐标相对位置与排序后的x坐标相对位置相同。
主要是排序，刚开始用的冒泡，超时，超时，超时.....后来干脆用C++库函数sort（），而且代码很简单，越来越感觉C++好用了.....
----------------AC-------------------------
#include <cstdio>
#include <algorithm>
int main()
{
int n, x[10001], y[10001];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &x[i], &y[i]);
std::sort(x, x + n);
std::sort(y, y + n);
for (int i = 0; i < n; i++)
x[i] -= i;
std::sort(x, x + n);
int s = 0;
for (int i = 0; i < n / 2; i++)
s += x[n - 1 - i] - x[i] + y[n - 1 - i] - y[i];
printf("%d\n", s);
return 0;
}
POJ 1723 SOLDIERS,布布扣,bubuko.com
原文：http://blog.csdn.net/zzucsliang/article/details/20923113