1018: 士兵排阵

时间限制: 1 Sec  内存限制: 128 MB

提交: 204  解决: 57

[] [] [] [命题人:外部导入]

题目描述

在一个划分成网格的操场上， n个士兵散乱地站在网格点上。 网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、 下、 左、 右移动一步， 但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择 x 和 y的值才能使士兵们以最少的总移动步数排成一列。 计算使所有士兵排成一行需要的最少移动步数。

输入

多组测试用例。

对于每一组测试用例,第1行是士兵数 n， 1≤n≤10000。 接下来 n行是士兵的初始位置， 每行有2个整数 x和 y，-10000≤x， y≤10000。

输出

数据的输出为一行， 表示士兵排成一行需要的最少移动步数。

样例输入

51 22 21 33 -23 3

样例输出

8

来源/分类

  

 

1 #include
        
          2 #include 
         
           3 #include 
          
            4 using namespace std; 5 int posx[10005]; 6 int posy[10005]; 7 //整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y) 8 //。如何选择 x 和 y的值才能使士兵们以最少的总移动步数排成一列 9 //如何才能使得移动的步数最少呢？其实这个问题可以拆开来看，x和y方向实际上10 //是互相不干扰的，我们可以分别求出x与y方向移动最少的点，先看y方向，所有的士兵11 //在y方向上都是在同一个y值的，所以只用先将所有士兵y方向上排序，排序后的中值12 //就是y方向上的最终值，再来看x方向上，由于在x方向上是连续的n个值，可以对每一个13 //值减去它在队伍里的偏差，转化成与y方向上一样的求法！14 //因此第一个士兵的移动距离是|x1-x|,第二个士兵的移动距离是|x2-x-1|，即到最优点x的15 //邻近点的位置，因此总距离为|x1-x|+|x2-x-1|+|x3-x-2|+...+|xn-n-n+1|,因此可求得最优点的x坐标为x1,x2-1...xn-n+1的中间值。16 17 int main(){18     int n;19     while (cin >> n){20         for (int i = 0; i 
           
            > posx[i] >> posy[i];22         }23         sort(posx, posx + n);24         sort(posy, posy + n);25         for (int j = 0; j