Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

此题的贪心算法,不知道对不对,欢迎讨论

Posted by jauhell at 2010-10-18 23:16:38 on Problem 1160
有下面几个假设:
(1) 对于 V 个村庄和 P 个邮局,最后肯定能将村庄分成 P 堆,每堆中连接到相同
的邮局。
(2) 如果将村庄按 x 坐标的位置排序,那么假设(1)中每一堆的村庄一定是相连的

那么我们可以这样来划分成 P 堆:
如果相邻的两个村庄 V[k] 和 V[k+1] 之间的距离 d(V[k], V[k+1] ) 大于其他任意
两相邻村庄之间的距离 d(V[i], V[i+1])  (i=1,2,3,....V-1)那么可以将 V[k]归于
前面的集合,V[k+1]归于后面的集合,如此分割 P-1 次即可得到 P 堆村庄
对于每堆中总距离是一定的,只要将邮局放在头和尾之间的村庄上就可以得到最
小的总距离

比如样例:
村庄位置:                    1     2     3      6      7     9     11     22     44     50
相邻村庄之间的距离:       1     1      3      1     2      2      11     22     6
去掉4个相邻距离最大的即可分成5堆,如下:
1,2,3      6,7,9,11     22     44       55
我们只要分别计算每堆的最短距离和,然后累加即可

PS:代码写了没过,不知道是自己代码细节有问题还是这种 思想不对,太晚了
也不想在查了,贴上我的一点想法 ,  欢迎大家讨论~

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator