题目链接

小红的有序数组

题目描述

小红有一个长度为 的排列，她每次可以选择两个数 和 ，要求 和 的奇偶性相同，然后交换这两个数。问最少需要多少次操作才能使得数组变成有序的，如果不能变的有序，输出 -1。

输入:

  • 第一行输入一个整数 ，表示数组的长度
  • 第二行输入 个整数 ，表示数组的元素

输出:

  • 如果能变成有序的，输出最少需要的操作次数，否则输出 -1

解题思路

这是一个贪心问题，可以通过以下步骤解决：

  1. 关键发现：

    • 只能交换相同奇偶性的数字
    • 这意味着奇数和偶数的相对位置不能改变
    • 最终数组要升序排列

  2. 解题策略：

    • 分别记录奇数和偶数的位置
    • 检查奇数和偶数的相对位置是否能满足最终升序要求
    • 如果可以，计算需要的最小交换次数

  3. 具体步骤：

    • 分别提取奇数序列和偶数序列
    • 检查每个序列内部是否可以通过交换变为有序
    • 计算每个序列内部需要的最小交换次数
    • 如果不能变为有序，输出-1

代码

#include <bits/stdc++.h>
using namespace std;

// 计算序列变为有序的最小交换次数
int minSwaps(vector<int>& arr) {
    int n = arr.size();
    vector<pair<int, int>> pos(n);
    for(int i = 0; i < n; i++) {
        pos[i] = {arr[i], i};
    }
    sort(pos.begin(), pos.end());
    
    vector<bool> vis(n, false);
    int ans = 0;
    
    for(int i = 0; i < n; i++) {
        if(vis[i] || pos[i].second == i) continue;
        
        int cycle_size = 0;
        int j = i;
        while(!vis[j]) {
            vis[j] = true;
            j = pos[j].second;
            cycle_size++;
        }
        ans += cycle_size - 1;
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<int> odd, even;
    vector<int> odd_pos, even_pos;
    
    // 分离奇数和偶数
    for(int i = 0; i < n; i++) {
        if(a[i] % 2) {
            odd.push_back(a[i]);
            odd_pos.push_back(i);
        } else {
            even.push_back(a[i]);
            even_pos.push_back(i);
        }
    }
    
    // 检查是否可能变为有序
    vector<int> sorted = a;
    sort(sorted.begin(), sorted.end());
    for(int i = 0; i < n; i++) {
        if((sorted[i] % 2) != (a[i] % 2)) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    // 计算最小交换次数
    int ans = minSwaps(odd) + minSwaps(even);
    cout << ans << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    // 计算序列变为有序的最小交换次数
    static int minSwaps(List<Integer> arr) {
        int n = arr.size();
        int[][] pos = new int[n][2];
        for(int i = 0; i < n; i++) {
            pos[i][0] = arr.get(i);
            pos[i][1] = i;
        }
        Arrays.sort(pos, (a, b) -> a[0] - b[0]);
        
        boolean[] vis = new boolean[n];
        int ans = 0;
        
        for(int i = 0; i < n; i++) {
            if(vis[i] || pos[i][1] == i) continue;
            
            int cycleSize = 0;
            int j = i;
            while(!vis[j]) {
                vis[j] = true;
                j = pos[j][1];
                cycleSize++;
            }
            ans += cycleSize - 1;
        }
        return ans;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> a = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        
        // 分离奇数和偶数
        for(int x : a) {
            if(x % 2 == 1) odd.add(x);
            else even.add(x);
        }
        
        // 检查是否可能变为有序
        List<Integer> sorted = new ArrayList<>(a);
        Collections.sort(sorted);
        for(int i = 0; i < n; i++) {
            if(sorted.get(i) % 2 != a.get(i) % 2) {
                System.out.println(-1);
                return;
            }
        }
        
        // 计算最小交换次数
        int ans = minSwaps(odd) + minSwaps(even);
        System.out.println(ans);
    }
}

def min_swaps(arr):
    n = len(arr)
    pos = list(enumerate(arr))  # (index, value)
    pos.sort(key=lambda x: x[1])
    
    vis = [False] * n
    ans = 0
    
    for i in range(n):
        if vis[i] or pos[i][0] == i:
            continue
            
        cycle_size = 0
        j = i
        while not vis[j]:
            vis[j] = True
            j = pos[j][0]
            cycle_size += 1
        ans += cycle_size - 1
    
    return ans

n = int(input())
a = list(map(int, input().split()))

# 分离奇数和偶数
odd = []
even = []
for x in a:
    if x % 2:
        odd.append(x)
    else:
        even.append(x)

# 检查是否可能变为有序
sorted_a = sorted(a)
for x, y in zip(sorted_a, a):
    if x % 2 != y % 2:
        print(-1)
        exit()

# 计算最小交换次数
ans = min_swaps(odd) + min_swaps(even)
print(ans)

算法及复杂度

  • 算法：贪心 + 最小交换次数
  • 时间复杂度： - 主要来自排序
  • 空间复杂度： - 需要存储奇偶数组和辅助数组