Question

acm pku 1723

http://acm.pku.edu.cn/JudgeOnline/problem?id=1723
题意是:给出n个士兵的坐标x,y,通过移送士兵,要求士兵站在同一行y坐标上,即士兵的最后位置是(x,y),(x+1,y),...(x+n-1,y),x,y为任意的.现要求士兵的最少移动次数..
我的做法是找出x,y的中位数xmid,ymid,将所有士兵的|Yi - ymid|相加,然后将各Xi从小到大排序,然后从第一个士兵开始放置在x坐标:( xmid - n/2 + i)上( i = 0,1,2,...n-1 ),求出 |Xi - ( xmid - n/2 + i )|相加的总和,再加上之前|Yi - ymid|的总和为答案..测试了一些数据都无误,但是提交却Wrong Answer..为什么这种做法有错? 即先求出Xi,Yi中位数,确定中间士兵的站位,然后再确定其他士兵的站位.

注意:我的问题是为什么我的做法有错,不要给我贴解题报告,那些解题报告我都已经看过

Answer 1

ymid 是 队伍的 位置没错了，

但是 xmid 不是 队伍的中心哦。

假设 n个士兵的 x 坐标是, x0,x1,.. x(n-1)
我们假设 他们 是 递增序列。

假设排好的队伍的 最左边的 x 坐标是 xl
那么我们的任务是 使
|xl-x0| + |xl+1-x1| +.... + | xl+n-1 -x(n-1) | 的值最小，

这个 表达式的 极值可不一定是取在 xl = xmid-n/2 的时候~

这个时候我们取 xnewmid 为
x0, x1-1, x2-2... x(n-1) - (n-1)
的平均值，

然后 使 xl = xnewmid

|xl-x0| + |xl+1-x1| +.... + | xl+n-1 -x(n-1) |

再加上 |Yi - ymid| 的总和 才是答案