acm pku 1723题意是:给出n个士兵的坐标x,y,通过移送士兵,要求士兵站在同一行y坐标上,即士兵的最后位置是(
acm pku 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中位数,确定中间士兵的站位,然后再确定其他士兵的站位.
注意:我的问题是为什么我的做法有错,不要给我贴解题报告,那些解题报告我都已经看过
题意是:给出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中位数,确定中间士兵的站位,然后再确定其他士兵的站位.
注意:我的问题是为什么我的做法有错,不要给我贴解题报告,那些解题报告我都已经看过
赞 W车主 幼苗
共回答了16个问题采纳率：93.8% 举报
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| 的总和 才是答案
但是 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| 的总和 才是答案
1年前
6
可能相似的问题
-
1年前2个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
你能帮帮他们吗