我真是太菜了。。。看了N个别人的解答,就是不懂。。直到这个出现,我终于懂了一点。。。。
首先考虑纵坐标:
对纵坐标做一次排序,那么,只要最终选择的纵坐标不小于最小的,且不大于最大的,那么对于一头一尾两个点,效果都是相同的;依此类推,所以,选择的纵坐标就是整个纵坐标序列的中位数了,简单吧?
再来考虑横坐标:
还是进行一次升序排列,很显然,这就是最终的顺序了(否则肯定会浪费移动次数),即:
X1 -> X0
X2 -> X0 + 1
...
Xn -> X0 + n - 1
也就是:
X1 -> X0
X2 - 1 -> X0
...
Xn - (n - 1) -> X0 //
来自
http://blog.sina.com.cn/s/blog_67ac571c0100itfv.html
下面是我自己的的代码了TVT~
1 #include<iostream>
2 #include<algorithm>
3 #include<cmath>
4 using namespace std;
5 //========================================
6 int x[10010];
7 int y[10010];
8 int main()
9 {
10 int n;
11 cin>>n;
12 int counts=0;
13 for(int i=0;i<n;++i)
14 {
15 cin>>x[i]>>y[i];
16 }
17 sort(y,y+n);
18 sort(x,x+n);
19 int yz=y[n/2];
20 for(int i=0;i<n;++i)
21 {
22 x[i]=x[i]-i;
23 }
24 sort(x,x+n);
25 int xz=x[n/2];
26 for(int i=0;i<n;++i)
27 {
28 counts+=(abs(y[i]-yz)+abs(x[i]-xz));
29 }
30 cout<<counts<<endl;
31
32
33
34 }