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

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

Posted by 200941842122zyq at 2011-08-24 11:21:49 on Problem 1160
In Reply To:此题的贪心算法,不知道对不对,欢迎讨论 Posted by:jauhell at 2010-10-18 23:16:38
> 有下面几个假设:
> (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