本文共 2487 字，大约阅读时间需要 8 分钟。

题目描述回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。交换的定义是：交换两个相邻的字符例如mamad第一次交换 ad : mamda第二次交换 md : madma第三次交换 ma : madam (回文！完美！)输入第一行是一个整数N，表示接下来的字符串的长度(N < = 8000)第二行是一个字符串，长度为N.只包含小写字母输出如果可能，输出最少的交换次数。否则输出Impossible样例输入5mamad样例输出3

知识点：贪心算法

1、贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 2、特性 贪婪算法可解决的问题通常大部分都有如下的特性:

⑴ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合:比如不同面值的硬币。

⑵ 随着算法的进行，将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

⑶ 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

⑷ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

⑸ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

⑹ 最后，目标函数给出解的值。

3、基本思路 ⒈）建立数学模型来描述问题。 ⒉）把求解的问题分成若干个子问题。 ⒊）对每一子问题求解，得到子问题的局部最优解。 ⒋）把子问题的解局部最优解合成原来解问题的一个解。

public class Daijia {
   	public static void main(String[] args) throws IOException{
   		Scanner scanner = new Scanner(System.in);	        int len = scanner.nextInt();	        char[] s = scanner.next().toCharArray();	        if (palindrome(s, 0, len - 1)) 	        {
   	            System.out.println(cnt);	        } 	        else 	        {
   	            System.out.println("Impossible");	        }	    }	     	    private static int cnt = 0;	    private static boolean haveMiddle = false;	     	    private static boolean palindrome(char[] s, int a, int b) 	    {
   	        if (b <= a) 	        {
   	            return true;	        }	                // 从最后的位置开始遍历字符串	        for (int i = b; i > a; i--) 	        {
   	            if (s[a] == s[i]) 	            {
   	                exchangeTo(s, i, b);	                cnt += getExchangeTimes(i, b);	                return palindrome(s, a + 1, b - 1);	            }	        }	                // 如果没有出现过中间字符	        if (!haveMiddle) 	        {
   	            haveMiddle = true;	            cnt += getExchangeTimes(a, s.length / 2);	            return palindrome(s, a + 1, b);	        }	        return false;	    }	     	    private static int getExchangeTimes(int a, int b) 	    {
   	        return b - a;	    }	     //交换从0位置开始，找到的第一个与0位置数，相同的 到最后一个	    //交换从1位置开始，找到的第一个与1位置数，相同的 到最后一个 +1;	    //if (palindrome(s, 0, len - 1)) 	    //return palindrome(s, a + 1, b - 1);	    private static void exchangeTo(char[] s, int a, int b) 	    {
   	        char temp = s[a];	        for (int i = a; i < b; i++) 	        {
   	            s[i] = s[i + 1];	        }	        s[b] = temp;        }         }

转载地址：http://bgrwi.baihongyu.com/