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

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

# 题目 #

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 (≤10 5 ^5 5) 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

# 分析 #

题目大意是：给定一组序列，规定只能每次用 0 去交换其他位置的数，问如果要排序，至少需要交换多少次  
用到表排序的思想：**N个数字的排列由若干个独立的环组成**  
什么意思呢？比如：a\[ \] = \{3 5 2 1 7 0 4 6\}，将a数组排序意思是要将正确的数放到正确的位置上去，a\[0\] = 3，而 3 的正确位置在 a\[3\]，而 a\[3\]=1，1 的正确位置在 a\[1\]，现在 a\[1\] = 5，5 的正确位置在 a\[5\]，而 a\[5\] = 0，a\[0\] 的正确位置就是 0，和最开始的 a\[0\] = 3 接上了，这就被称为一个环  
由于是用 0 去交换其他值，所以总共有三种环：

1.  环内只有一个元素，即该数已经在正确的位置上了，不需要交换，比如上面的 a\[2\] = 2
2.  环内有 n 个元素，含 0，需要交换次数是：n-1 （每一个非 0 元素都要和 0 换一下）
3.  环内有 n 个元素，不含 0，需要交换的次数是：n+1（把 0 换入换出+其余 n-1 个非 0 元素和 0 换一下）

交换的次数就是各种环交换的总数

#include<iostream>
    #include<vector>
    using namespace std;
    int main(){
        
      int N;
      cin>>N;
      int tmp;
      int sum = 0;
      vector<int> A; // 存 N 
      vector<bool> flag;
      for(int i=0;i<N;i++){
        
      	cin>>tmp;
      	A.push_back(tmp);
      	flag.push_back(false);
      }
      for(int i=0;i<N;i++){
        
      	if(A[i]!=i && !flag[i]){
           // 没被访问过的单元环 
      		int tmpSum = 0;  // 计交换次数
      		int j = i;
      		do{
        
      			tmpSum++;  // 每遇到一个数计数+1 
      			flag[j] = true; // 标记环 
      			if(!A[j])   // 如果遇到了 0，减去入环出环的两次 
      				tmpSum-=2;
      			j = A[j];
      		}while(j!=i);
      		tmpSum++;    // 前面减去了 0，所以交换次数是当前数个数+1 
      		sum += tmpSum;
      	}
      }
      cout<<sum<<endl;
      return 0;
    }