题目

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​​ <math> <semantics> <mrow> <msup> <mn> 5 </mn> </msup> </mrow> <annotation encoding="application&#47;x&#45;tex"> ^5 </annotation> </semantics> </math>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;
}