acm pku 1723题意是:给出n个士兵的坐标x,y,通过移送士兵,要求士兵站在同一行y坐标上,即士兵的最后位置是(x,y),(x+1,y),...(x+n-1,y),x,y为任意的.现要求士兵的最少移动次数..我的做法是找出x,y的中位
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/28 20:54:35
![acm pku 1723题意是:给出n个士兵的坐标x,y,通过移送士兵,要求士兵站在同一行y坐标上,即士兵的最后位置是(x,y),(x+1,y),...(x+n-1,y),x,y为任意的.现要求士兵的最少移动次数..我的做法是找出x,y的中位](/uploads/image/z/8789446-46-6.jpg?t=acm+pku+1723%E9%A2%98%E6%84%8F%E6%98%AF%3A%E7%BB%99%E5%87%BAn%E4%B8%AA%E5%A3%AB%E5%85%B5%E7%9A%84%E5%9D%90%E6%A0%87x%2Cy%2C%E9%80%9A%E8%BF%87%E7%A7%BB%E9%80%81%E5%A3%AB%E5%85%B5%2C%E8%A6%81%E6%B1%82%E5%A3%AB%E5%85%B5%E7%AB%99%E5%9C%A8%E5%90%8C%E4%B8%80%E8%A1%8Cy%E5%9D%90%E6%A0%87%E4%B8%8A%2C%E5%8D%B3%E5%A3%AB%E5%85%B5%E7%9A%84%E6%9C%80%E5%90%8E%E4%BD%8D%E7%BD%AE%E6%98%AF%28x%2Cy%29%2C%28x%2B1%2Cy%29%2C...%28x%2Bn-1%2Cy%29%2Cx%2Cy%E4%B8%BA%E4%BB%BB%E6%84%8F%E7%9A%84.%E7%8E%B0%E8%A6%81%E6%B1%82%E5%A3%AB%E5%85%B5%E7%9A%84%E6%9C%80%E5%B0%91%E7%A7%BB%E5%8A%A8%E6%AC%A1%E6%95%B0..%E6%88%91%E7%9A%84%E5%81%9A%E6%B3%95%E6%98%AF%E6%89%BE%E5%87%BAx%2Cy%E7%9A%84%E4%B8%AD%E4%BD%8D)
acm pku 1723题意是:给出n个士兵的坐标x,y,通过移送士兵,要求士兵站在同一行y坐标上,即士兵的最后位置是(x,y),(x+1,y),...(x+n-1,y),x,y为任意的.现要求士兵的最少移动次数..我的做法是找出x,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中位数,确定中间士兵的站位,然后再确定其他士兵的站位.
注意:我的问题是为什么我的做法有错,不要给我贴解题报告,那些解题报告我都已经看过
acm pku 1723题意是:给出n个士兵的坐标x,y,通过移送士兵,要求士兵站在同一行y坐标上,即士兵的最后位置是(x,y),(x+1,y),...(x+n-1,y),x,y为任意的.现要求士兵的最少移动次数..我的做法是找出x,y的中位
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| 的总和 才是答案