@Aqua-Dream 2016-10-19T01:30:12.000000Z 字数 2950 阅读 1087

# 浙大PAT-Sort with Swap(0, i)

算法

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.

Input Specification:
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.

Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:
10
3 5 7 2 6 4 9 0 8 1

Sample Output:
9

$a_0,a_1,a_2,…,a_{n-1}$$0,1,2,…,n-1$的一个置换，交换0与$a_i$称为一次交换操作，下面将给出把$a_0,a_1,a_2,…,a_{n-1}$利用交换操作变成$0,1,2,…,n-1$所需的最小操作次数以及具体方法。

0 1 2 $n-1$
$a_0$ $a_1$ $a_2$ $a_{n-1}$

0 1 2 3 4 5 6 7 8 9
3 5 7 2 6 4 9 0 8 1

0->3->2->7->(0)
1->5->4->6->9->(1)
8->(8)

0->3->2->7->(0)
1->5->4->6->9->(1)
8->(8)

0->2->7->(0)
1->5->4->6->9->(1)
8->(8)
3->(3)

0->(0)
1->5->4->6->9->(1)
8->(8)
3->(3)
2->(2)
7->(7)

0->5->4->6->9->1->(0)
8->(8)
3->(3)
2->(2)
7->(7)

#include <iostream>using namespace std;int search(int* p, int num){    static int first = 1;    for (int i = first; i<num; i++)        if (p[i] != i)            return first = i;    return 0;}void swap(int* p, int n){    int temp = p[0];    p[0] = p[n];    p[n] = temp;}int main(){    int n;    cin >> n;    int *data = new int[n];    int temp;    for (int i = 0; i<n; i++)    {        cin >> temp;        data[temp] = i;    }    int count = 0;    while (true)    {        if (data[0])            swap(data, data[0]);        else        {            temp = search(data, n);            if (!temp) break;            swap(data, temp);        }        count++;    }    cout << count << endl;    delete[] data;    return 0;}

• 私有
• 公开
• 删除