Re: [問題] Costed Sorting 的演算法
: → ykjiang:如允許先找出 sorted sequence ，有方法， 61.59.12.146 11/13 12:44
: → ykjiang:使最糟情況只要swap n次，n為元素個數 61.59.12.146 11/13 12:45
: → ykjiang:若否，你需要的是挑一個 nlogn 的演算法 61.59.12.146 11/13 12:52
我應該知道這邊推文說的是什麼方法...
那是這樣的 我們先找出 sorted sequence
以剛剛的 18976 來說
1 8 9 7 6
1 6 7 8 9
如果把同位置的原數和目標數串起來的話 這裡會串出兩圈來:
1 -> 1 ; 6 -> 9 -> 7 -> 8 -> 6 長度分別是 1,4
也就是 不看 cost 的話我們只要對換 (6,9),(6,7),(6,8)
但如果算上 cost 的話 這裡需要的 cost 就是 圈中最小數x(圈長度-1)+圈中其餘數和
所以這時套用前幾篇回文的想法 引入一個比較小的數
變成對換 (1,6),(1,9),(1,7),(1,8),(1,6)
這樣的 cost 就是 較小數x(圈長度+1)+(圈中數字和+圈中最小數)
那麼對於每個串出來的圈就用兩個方法中 cost 比較小的那一個來做
這樣應該是個還不錯的做法...
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
推
11/13 14:56, , 1F
11/13 14:56, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 7 篇)：