-->
当前位置:首页 > 题库

PROGRAMMING:Exchange with zero

Luz5年前 (2021-05-10)题库458
It's not difficult to sort any permutation of {0, 1, 2,..., n-1}. To add a little difficulty here, you can only increase the initial sequence by a series of swap (0, *) - that is, exchange a number with 0. For example, for the initial sequence {4, 0, 2, 1, 3}, we can complete the sorting by the following operations:
- Swap(0, 1) $$\Longrightarrow$$ { 4, 1, 2, 0, 3 }
- Swap(0, 3) $$\Longrightarrow$$ { 4, 1, 2, 3, 0 }
- Swap(0, 4) $$\Longrightarrow$$ { 0, 1, 2, 3, 4 }
This problem requires you to find the first n non negative integers of a given permutation for incremental sorting required by the minimum number of exchanges with 0.
###Input format:
Enter the positive integer n ($$$Le 10 ^ 5 $$) in the first line; The next line gives an arrangement of {0, 1, 2,..., n-1}. Numbers are separated by spaces.
###Output format:
In one row, output the minimum number of exchanges with 0 required to sort a given sequence incrementally.
###Input example:
```in
ten
3 5 7 2 6 4 9 0 8 1
```
###Output example:
```out
nine
```







answer:If there is no answer, please comment