https://codeforces.com/contest/1810/problem/Bhttps://codeforces.com/contest/1810/problem/B
时间: 2023-09-29 22:08:59 浏览: 63
Problem:
You are given an array a of n integers. You can perform the following operation any number of times: choose two distinct indices i and j (1≤i,j≤n) such that ai≠aj and replace ai with aj and aj with ai.
An array is called beautiful if it is sorted in non-decreasing order (a1≤a2≤…≤an).
Find the minimum number of operations needed to make the given array beautiful.
Solution:
Observation: If we can't make the array beautiful, output -1.
Let's assume we have a beautiful array as b.
If we swap two distinct indices i and j in array a, then b will also have swapped elements b[i] and b[j]. So, we need to find the minimum number of swaps required to convert array a to array b.
We can do this by counting the number of inversions in array a. An inversion is a pair of indices (i,j) such that i<j and ai>aj. The number of inversions in array a is equal to the number of swaps required to sort the array in non-decreasing order.
If the number of inversions is odd, we can't make the array beautiful.
If the number of inversions is even, then we can make the array beautiful. The minimum number of swaps required is equal to the number of inversions.
Time Complexity: O(n log n)
Space Complexity: O(n)
Implementation:
- First, we count the number of inversions in array a using merge sort.
- If the number of inversions is odd, output -1.
- Otherwise, output the number of inversions.