推 FRAXIS: 這是 Eucldean TSP 嗎？ 03/29 11:09
→ rareone: Nope 是用莫隊想法 03/29 13:10
推 oToToT: 前幾天也剛好看到這題XD 03/30 07:55
題幹：平面給 N 個點，輸出一條 circuit 走過所有點一次，而且長度小於等於 2.5e9
條件 (x, y) in [0, 1e6] X [0, 1e6], N <= 1e6
作法：
我一開始看到這題的時候真的用莫隊下去切，也沒有分析一下複雜度，就這樣踩到雷
我的莫隊是這樣 implement 的：
key = make_pair(x / SQRT, y)
sort points by key
分析一下為何錯誤：
SQRT = sqrt(1e6) = 1000
莫隊把 x 軸分成約 SQRT 塊，每一塊的 cost 右界移動最多是 1e6
** 塊跟塊之間的轉移 cost 是 1e6（右界指標要回來）**
光右界就能輕鬆造出 2e9
左界移動每次幅度大可以到 SQRT （外加 O(N) 均攤，倒不是很關鍵）
左屆總計也差不多 1e9 剛好吃 WA
如果交錯右屆可以磨掉 ** 之間的 cost 也就是：
key = make_pair(x / SQRT, x / SQRT % 2 ? y : -y)
sort point by key
偷看了一下測資，的確沒有 cost 是大於 2e9 ，很接近倒是有
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.216.110
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1553789929.A.B3C.html