作者Starwindd (我是G爹)
看板Programming
标题[问题] Costed Sorting 的演算法
时间Sat Nov 13 04:04:50 2010
请教一下costed sort的作法... 一个头两个大...
基本要求是这样，给一串数字，用两两交换的方式来sort，但是每个sort要
花代价...
例如 sort {3, 2, 1}
先把 1,2 对调变成 {3, 1, 2} -> 代价为 1+2 =3
然後把 1,3 对调 {1, 3, 2} -> 代价为 1+3 =4
最後换 2,3 {1, 2, 3} -> 代价为 2+3 =5 => 总代价为 12
题目要求要找出最小代价的算法，以这题来说当然是 1 跟 3 直接对调，总代价 = 4
我一开始的想法是先sort找出最後的正确数列，然後从最小代价的数字组开始互换
，直到数列正确。例如
8124 -> 8214(3 cost) -> 8241(cost 5) -> 1248(cost 9)
但是遇到数字跳很大的就出问题了，例如18976
我的作法会是
18976 -> 16978 (14) -> 16798 (16) -> 16789 (17) = 47
但正确的最小代价解法是
18976 -> 68971 (7) -> 68179 (10) -> 68719 (8) -> 61789 (9) -> 16789 (7) = 41
这样的问题到底该怎麽解呢？
--
英文翻译： Are you longsome tonight?
版本 A： 今晚，你是龙神吗？
版本 B： 你是龙神吐奶吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 75.143.81.79
1F：→ ykjiang:如允许先找出 sorted sequence ，有方法， 61.59.12.146 11/13 12:44
2F：→ ykjiang:使最糟情况只要swap n次，n为元素个数 61.59.12.146 11/13 12:45
3F：→ ykjiang:若否，你需要的是挑一个 nlogn 的演算法 61.59.12.146 11/13 12:52