python 实现pat Sort with Swap(0,*)

ゝ一世哀愁。 2022-06-04 02:16 108阅读 0赞

### 题目 Sort with Swap(0,\*) (25) ###

Given any permutation of the numbers \{0, 1, 2,…, N-1\}, it is easy to sort them in increasing order. But what if Swap(0, \*) is the ONLY operation that is allowed to use? For example, to sort \{4, 0, 2, 1, 3\} we may apply the swap operations in the following way:

Swap(0, 1) => \{4, 1, 2, 0, 3\}

Swap(0, 3) => \{4, 1, 2, 3, 0\}

Swap(0, 4) => \{0, 1, 2, 3, 4\}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.  
输入描述:

Each input file contains one test case, which gives a positive N (<=105) followed by a permutation sequence of \{0, 1, …, N-1\}. All the numbers in a line are separated by a space.

输出描述:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.  
示例1  
输入

10 3 5 7 2 6 4 9 0 8 1  
输出

9

### 解答 ###

line=[int(x) for x in input().split(' ')]
    N=line[0]
    nums=line[1:]
    index=0
    swaps=0
    visited=[False]*N
    #先计算有0环元素个数
    while (nums[index] != 0):
        index = nums[index]
        visited[index] = True
        swaps+=1
    #print (swaps)
    # 再计算无0环元素个数
    for i in range(1,N):
        if (visited[i] == False and nums[i] != i):
            swaps += 1
            index = i
            visited[index] = True
            swaps += 1
            while ( nums[index] != i):
                index = nums[index]
                visited[index] = True
                swaps += 1
    print (swaps)

发表评论取消回复

表情：

评论列表（有 0 条评论，108人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT 甲级 1067 Sort with Swap(0, i) (25 分) 代码10分钟，bug 1晚上+1小时果然还是状态最重要

1067 Sort with Swap(0, i) (25 分) Given any permutation of the numbers \{0, 1, 2,...,

电玩女神/ 2024年02月19日 21:54/ 0 赞/ 9 阅读

相关 PAT 甲级 1028 List Sorting (25 分) STL +sort

1028 List Sorting (25 分) Excel can sort records according to any column. Now you are

灰太狼/ 2024年02月19日 21:29/ 0 赞/ 67 阅读

相关 1067. Sort with Swap(0,*) (25)

下面是自己写的，但是只得了19分，有两个点超时 <span style="font-size:14px;">include<iostream> using n

系统管理员/ 2022年08月13日 18:32/ 0 赞/ 109 阅读

相关 Python实现Pat 1028. List Sorting (25)

[题目][Link 1] A traveler’s map gives the distances between cities along the highways,

水深无声/ 2022年06月04日 08:14/ 0 赞/ 203 阅读

相关 Python实现Pat 1023. Have Fun with Numbers (20)

[题目][Link 1] Notice that the number 123456789 is a 9-digit number consisting exactly

ゞ浴缸里的玫瑰/ 2022年06月04日 08:07/ 0 赞/ 218 阅读

相关 python 实现pat Sort with Swap(0,*)

题目 Sort with Swap(0,\) (25) Given any permutation of the numbers \{0, 1, 2,…, N-1\},

ゝ一世哀愁。/ 2022年06月04日 02:16/ 0 赞/ 109 阅读

相关 1067. Sort with Swap(0,*) (25)

Given any permutation of the numbers \{0, 1, 2,..., N-1\}, it is easy to sort them in in

怼烎@/ 2022年05月30日 00:45/ 0 赞/ 115 阅读

相关 Algorithm - Swap Sort（Java）

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.cap

￡神魔★判官ぃ/ 2022年05月23日 06:39/ 0 赞/ 192 阅读

相关《数据结构》10-排序6 Sort with Swap(0, i)

题目 Given any permutation of the numbers \{0, 1, 2,…, N−1\}, it is easy to sort them i

阳光穿透心脏的1/2处/ 2022年04月14日 03:21/ 0 赞/ 130 阅读

相关 PAT 1067 Sort with Swap(0, i) (贪心法)

Given any permutation of the numbers \{0, 1, 2,..., N−1\}, it is easy to sort them in in

梦里梦外;/ 2022年04月10日 14:41/ 0 赞/ 165 阅读