POJ 1723

我真是太菜了。。。看了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 }




posted on 2011-11-22 21:24 四也 阅读(369) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜