#31889: 答:為何不可以從前k - 1大的間隔分割得到最佳解


seer852741@gmail.com (St418)

School : 國立中央大學
ID : 170226
IP address : [114.24.161.39]
Last Login :
2024-01-05 19:57:56
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [220.129.108.132] | Post Date : 2022-08-25 23:45

詳細解法請看另一篇

 

大部分人的想法都是這樣:

  1. 計算出可能的直徑範圍
  2. 建立測試指定直徑是否滿足規範的函式
  3. 二元搜的方式找出滿足條件的最小直徑

 

這個方法的確能夠過關,但我也有看到有人提出:

  1. 找到前k-1大的兩服務點距離
  2. 分割成數個小組
  3. 找出直徑最大的小組便是答案

 

假設「k = x + 1時最佳解的情形是k = x的延伸」,

也就是k = x + 1個基地台能得到最小直徑的分布情形,是由k = x時的最佳分布情形所產生的,

並且產生方式是從最大間隔處進行分割。

 

示意圖:

服務點為[1 2 5 7 8],間隔為[1 3 2 1]

k = 1,d = 7,1 2 5 7 8

k = 2,d = 3,1 2 | 5 7 8

k = 3,d = 1,1 2 | 5 | 7 8

 

的確符合敘述,但反例也很好找:

服務點為[2 3 5 8 12 17],間隔為[1 2 3 4 5]

k = 1,d = 6,2 3 5 8 | 12 17

k = 2,d = 4,2 3 5 | 8 12 | 17

k = 3,d = 2,2 3 5 | 8 | 12 | 17 或 2 3 | 5 8 | 12 | 17

 

既不是從最大的間隔點切割,也不符合「k = x + 1時最佳解的情形是k = x的延伸」的假設。

 
ZeroJudge Forum