※ 引述《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)