当前位置:首页 > 排序 > 正文
SSOJ2299士兵站队问题
834+

题目大意:在一个网格操场上,士兵分散站着,现在要排除紧密的一行,士兵们至少总共走多少步?

题目描述

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

编程任务:计算使所有士兵排成一行需要的最少移动步数。

输入

输入士兵数n,1<=n<=10000。接下来n 行是士兵的初始位置,每行2 个整数x 和y,-10000<=x,y<=10000。

输出

输出的第1 行中的数是士兵排成一行需要的最少移动步数。

样例输入

5
1 2
2 2
1 3
3 -2
3 3

样例输出

8

解题思路

1、确定纵坐标b的值:所有士兵都走到y=b这一行,那么b是所有y坐标中的中位数,代价为|y[1]-m|+|y[2]-m|+…+|y[n]-m|。对于这一行的纵坐标,如果往上偏移,那么“线上”的士兵都少走一步,“线下”的士兵都多走一步。只要线两边的士兵不平衡,只需要慢慢的让这条线往士兵多的一边偏移,步数就会减少。只有线两边士兵数量相同,步数最少。(奇数、偶数一样)

2、横坐标区域,可以枚举区域左端点l,然后最左边的士兵移到l,第二左边的士兵移到l+1……每个士兵移动的步数加起来就是代价(不超时)。

3、横坐标代价计算优化:x[1]-l + x[2]-(l+1) + … + x[n]-(l+n-1) 即x[1]-0-l + x[2]-1-l + … + x[n]-(n-1)-l,如果把横坐标x[i]全部转换成x[i]-(i-1),那么问题就相当于所有士兵移动到新的横坐标的中位数的问题了。

程序实现

暴力拿分代码:

更多

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ2299士兵站队问题:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter