시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 233 | 182 | 157 | 78.500% |
You are given an array [p[1], p[2], ..., p[n]] where all the numbers in the array are distinct. In addition, the numbers are positive integers between 1 and n. You can only perform the following operations on the array: Pick two indices x and y such that |p[x]−p[y]| = 1, and then swap the values of p[x] and p[y]. We now want to sort this array in ascending order. That is, to make p[i] = i for all i ∈ {1, 2, ..., n}. For example, we can sort the array [p[1] = 2, p[2] = 3, p[3] = 1] in two operations:
Please write a program to compute the minimum number of operations to sort a given array in ascending order.
The input contain two lines. The first line contains one integer n. The second lines contain n space-saparated numbers p[1], p[2], ..., p[n] representing the array [p[1], p[2], ..., p[n]].
Output only one number that denotes the minimum number of operations required to sort the given array.
3 1 3 2
1
5 5 3 2 1 4
7
ICPC > Regionals > Asia Pacific > Taiwan > Taiwan Online Programming Contest > TOPC 2021 C번