Re: [問題] Costed Sorting 的演算法
偷推 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 比較少的方式來處理就好
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.144.168
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 6 之 7 篇)：