蓝桥杯 BASIC-19 VIP试题 完美的代价 贪心算法

分析：
首先判断字符串是否能构成回文串：
不能构成回文串的话直接输出Impossible。

只要只出现奇数次的字母个数多于1个就不能构成回文串。

能构成回文串的话再用递归的方法统计需要移动的最小次数。

代码如下

import java.util.Scanner;

public class Main {
    public static boolean IsPossible(String str) { // 判断字符串是否能构成回文串
        boolean flag = true;
        char[] s = str.toCharArray();
        int[] num = new int[26];

        for (int i = 0; i < str.length(); i++) {
            num[s[i] - 'a']++;
        }

        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (num[i] % 2 == 1)
                count++;
        }
        if (count > 1)
            return false;
        return flag;
    }

    public static int getCount(String str) { // 调换成回文串需要交换的次数
        if (str.length() == 1 || str.length() == 2)
            return 0;
        int temp = str.lastIndexOf(str.charAt(0));
        if (temp == 0) {
            return str.length() / 2 + getCount(str.substring(1, str.length()));
        } else {
            // temp不为0说明首字符有匹配的字母，移除首字母及其对应字母
            // 返回将temp位置的字符移动到末位置的次数（str.length()- temp - 1）
            // 递归调用getResult（）方法
            StringBuilder sb = new StringBuilder(str);
            sb.deleteCharAt(temp);
            sb.deleteCharAt(0);
            return str.length() - temp - 1 + getCount(sb.toString());
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str = sc.next();

        if (IsPossible(str)) {
            System.out.println(getCount(str));
        } else {
            System.out.println("Impossible");
        }

        sc.close();
    }
}

演示效果如下--

希望能对大家有所帮助！

谢谢大家！