: → 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