运动世界校园melon怎么看有效次数数?

0

  题目大意: 给你一个乱序的序列(permutation )从0到N-1,顺序打乱下面给你一种交换排序的算法:每次交换只能和元素0进行交换,交换一定次数之后达到升序。请问最小的茭换次数
  解题思路: 题目限定只能和0元素交换,且要达到最小交换次数所谓最小交换次数,我们务必保证每一次交换都是最有效率的如何才算是最有效率呢?一次交换确定一个元素的最终位置
  因为每次交换都要用到0元素,不妨把0元素作为一个运载体每交換一次,0元素把一个元素送到最终位置
  那么不妨考虑从0到N-1开始遍历,每次考察第i个元素是否在自己位置上如果在,则跳过如果鈈在,则用0元素与其交换;
  交换之前考察0元素所指向的位置,如果0元素不在0号位置上那么先把占用0号位置的其他元素送回到自己該处的位置;
  0号元素已经回归到自己的位置上时,再送第i号元素回第i号位置;
  由于每次都要用到0号元素和0号位置所以遍历可以從1开始,而不是0.


  都说这道题是基于贪心策略的但是我却没有发现哪一点体现贪心思想了,可能是我对贪心的理解不够深吧

我要回帖

更多关于 melon怎么看有效次数 的文章

 

随机推荐