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. 输入例子: 10 3 5 7 2 6 4 9 0 8 1 输出例子: 9
#include
using
namespace
std;
void
swap0_all(
int
*a,
int
*b) {
if
(*a==
0
) {
*a = *b;
*b =
0
;
}
else
if
(*b==
0
){
*b = *a;
*a =
0
;
}
else
{
return
;
}
}
int
check(
int
*in,
int
len) {
for
(
int
i =
1
; i < len; i++) {
if
(in[i]!=i) {
return
i;
}
}
return
0
;
}
int
main() {
int
NUM;
int
count =
0
;
cin >> NUM;
int
*array =
new
int
[NUM];
int
*index =
new
int
[NUM];
for
(
int
i=
0
; i cin >> array[i]; index[array[i]] = i; } int zero_pos = index[ 0 ]; int tar_pos = index[zero_pos]; for (;;) { if (zero_pos!= 0 ) { swap0_all(array+zero_pos,array+tar_pos); zero_pos = tar_pos; tar_pos = index[zero_pos]; count++; } else { tar_pos = check(array,NUM); if (tar_pos== 0 ) { break ; } else { index[array[tar_pos]] = 0 ; index[ 0 ] = tar_pos; swap0_all(array+zero_pos,array+tar_pos); count++; zero_pos = tar_pos; tar_pos = index[zero_pos]; } } } cout << count << endl; delete [] array; delete [] index; return 0 ; }
