`The input consists of natural number N and M (N <= 2*10^5 and M < N).`↵
↵
~~~~~↵
Then you are given a permutation of numbers [1, N]↵
You should sort the given array, but only the following operation is allowed:↵
Chose a number with index from [0, M-1] and choose a number from [M, N-1], then swap then.↵
What is the minimum number of operations to sort the array?↵
~~~~~↵
↵
Example:↵
**Input:** ↵
5 3↵
↵
1 2 3 5 4↵
**Steps:**↵
- 1 2 5 3 4 (swap 3 and 5)↵
- 1 2 4 3 5 (swap 4 and 5)↵
- [1 2 3 4 5] (swap 3 and 4, now the array is sorted, total steps = 3)↵
~~~~~↵
5 3↵
1 2 3 5 4↵
~~~~~↵
↵
~~~~~↵
**Steps:**↵
1. 1 2 5 3 4 (swap 3 and 5)↵
2. 1 2 4 3 5 (swap 4 and 5)↵
3. [1 2 3 4 5] (swap 3 and 4, now the array is sorted, total steps = 3)↵
~~~~~↵
↵
↵
↵
Any idea on how to solve this problem?
↵
~~~~~↵
Then you are given a permutation of numbers [1, N]↵
You should sort the given array, but only the following operation is allowed:↵
Chose a number with index from [0, M-1] and choose a number from [M, N-1], then swap then.↵
What is the minimum number of operations to sort the array?↵
~~~~~↵
↵
Example:↵
**Input:** ↵
↵
1 2 3 5 4↵
**Steps:**↵
- 1 2 5 3 4 (swap 3 and 5)↵
- 1 2 4 3 5 (swap 4 and 5)↵
- [1 2 3 4 5] (swap 3 and 4, now the array is sorted, total steps = 3)
~~~~~↵
5 3↵
1 2 3 5 4↵
~~~~~↵
↵
~~~~~↵
**Steps:**↵
1. 1 2 5 3 4 (swap 3 and 5)↵
2. 1 2 4 3 5 (swap 4 and 5)↵
3. [1 2 3 4 5] (swap 3 and 4, now the array is sorted, total steps = 3)↵
~~~~~↵
↵
↵
↵
Any idea on how to solve this problem?
