作者bleed1979 (十三)
站內Programming
標題Re: [問題] Costed Sorting 的演算法
時間Mon Dec 6 23:57:27 2010
※ 引述《suhorng ( )》之銘言：
: 偷推 LPH 大的做法XD"
: 是 ACM/ICPC World Finals 2001/2002 這題吧
: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2481
: 今年選訓營模考還出過這題所以印象深刻....XD
: 假設輸入的是 1 8 9 7 6
: 那把我們要排完的目標對應起來:
: 1 8 9 7 6
: 1 6 7 8 9
: 會發現形成很多個圈 (1) (8 6 9 7)
: 對一個圈有兩種處理方式：
: 1) 單純用圈中最小元素來交換
: 2) 先讓圈外的一個最小的元素跟圈內最小元素交換，用這個元素去把圈中的
: 所有元素換到位
: 那對所有圈都用 cost 比較少的方式來處理就好
上面的連結和SPOJ2277都是一樣的題目，有興趣的人可以嘗試。
我補充說明一下2點。
1.前置動作是如果兩個數交換一次即可讓兩個數都回到正確位置，就必須先做。
ex.
1 2 3 8 6 7 5
1 2 3 5 6 7 8
很明顯8和5交換一次就各自回到正確的位置。
2.圈的定義。
所有數中的最小數(all_s)或尚未回到正確位置的最小數(undo_s)，
在其回到正確位置所經歷的所有數構成一個圈。
all_s有可能是undo_s，undo_s可以有很多個。
ex.
1 8 9 7 6
all_s = 1, undo_s = 6, circle = 8 9 7 6
8 1 4 2
all_s = 1, undo_s = 1, circle = 8 1 2
critical的測資如下：
1 3 7 5 6 4 2
all_s = 1, undo_s1 = 2, undo_s2 = 4, circle1 = 3 7 2, circle2 = 5 6 4
cost = 33
undo_s要依序(較小的undo_s優先)，
同一時間就是all_s和undo_sx兩個比。
剩下的就如同上面討論的，公式代入找比出來較小的那一個做。
Bleed
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.124.60
※ 編輯: bleed1979 來自: 114.43.124.60 (12/07 00:00)