作者suhorng ( )
站内Programming
标题Re: [问题] Costed Sorting 的演算法
时间Sun Nov 14 18:40:18 2010
偷推 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