关于网易内推编程题堆棋子的解法
第一题堆棋子，当场对角懵逼、拉格朗日懵逼、。。。然后就自然而然地跪了= =。心态很重要，心态炸了一切都完了。
后来跟室友讨论了一下，算是完整的找到了一个解法，然后上来翻帖子发现精品贴已经贴出来了，思路完全一样，但是缺少说明和证明，所以在这里补充一下。
首先得证明这么一个问题，当给定i个棋子的坐标后，最后全部汇聚到一个格子，使总移动步数最少，则这个格子的横坐标应该是所有i个棋子的横坐标的中位数，纵坐标应该是所有i个棋子的纵坐标的中位数（但是要注意该点不一定是i个点之一，这个比较容易被忽略）。室友提出来的，当时我就震惊了，膜拜一下室友。具体证明起来我表达能力较差，直接拋一个博客链接好了：http://blog.csdn.net/zhang20072844/article/details/13372753
曼哈顿距离有意思的地方就在于求和的时候可以把x和y解耦，然后分别考虑。退化到一维后，把上面链接中带权中位数的各权值设为1即可。文中给出的证明我没看（太长不看。。。），其实一维的问题画图很容易证明，给个思路：考虑第一个数和最后一个数的距离、第二个数和倒数第二个数的距离、...。
好了，上面的问题解决后，剩下的就相对简单了。不过有的人可能会想，既然给定i个点后汇聚点的坐标求法知道了，但是一共有n个点啊，选出i个点出来也相当麻烦呢，这里给出的回答是不用选。由于不管i取何值，以及怎么选出这i个点，最后的汇聚点的横坐标一定是n个点的横坐标之一，纵坐标一定是n个点的纵坐标之一，所以只需考虑这n*n种情况就可以了。这其实帮助我们把搜索目标从n个点的矩形包络的量级缩减到了n*n的量级。
最后，设一个有n*n行，n列的矩阵res，每一行存储n*n种汇聚点之一到n个点的曼哈顿距离，然后对每一行从小到大排序，然后逐行依次把第i列赋值为前i-1列数值之和。这时候的矩阵所存储的，其实是对于每一种汇聚点（对应每一行），把离其最近的i个点汇聚过来所需要的总步数。所以，最后的最后，对矩阵逐列求最小值，即为答案。
下面贴出C++的代码，变量命名一塌糊涂，见谅。。。（有一个优化策略，就是n个点的所有横坐标（以及纵坐标，道理一样）中，可能有重复值，这时只用选取一次即可，类似于求一个unique，但是对STL不太熟，就没做= =）
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int x[n];
int y[n];
for(int i=0;i<n;i++)
cin>>x[i];
for(int i=0;i<n;i++)
cin>>y[i];
int res[n*n][n];
//计算n个点到n*n个候选目标点的距离
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++){
res[i*n+j][k] = abs(x[i]-x[k])+abs(y[j]-y[k]);
}
//对每个候选目标点到输入的n个点的距离排序（即对res的每一行排序）
for(int i=0;i<n*n;i++)
sort(*res+i*n,*res+(i+1)*n);
//res的第i列，赋值为前i-1列之和，即距其最近的i个点移到该目标点的总移动次数
for(int i=0;i<n;i++){
if(i==0)
continue;
for(int j=0;j<n*n;j++){
res[j][i]+=res[j][i-1];
}
}
//求res每一列的最小值，即为答案
for(int i=0;i<n;i++)
for(int j=0;j<n*n-1;j++)
res[0][i] = min(res[0][i],res[j+1][i]);
for(int i=0;i<n;i++)
i==0?cout<<res[0][i]:cout<<' '<<res[0][i];
return 0;
} #网易##算法工程师#
投递比亚迪等公司10个岗位 >