【蓝桥杯】完美的代价，贪心算法详解

Love The Way You Lie 2023-07-06 13:05 18阅读 0赞

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

样例输入  
5

mamad  
样例输出  
3

## 分析 ##

### 贪心算法 ###

**最优子结构:**  
mamad最小步骤包括  
变成a( … )a的步骤+(…)的最小步骤  
或者m(…)m的步骤+(…)的最小步骤  
另外如果是奇数个可以把单独的那个提出了化成偶数个字符,同样也是由子结构  
**贪心选择:**  
要总的最小步骤那么每次变成a(…)a的形式的步骤最小  
那么久按照从外到内的顺序,m在最外部,首先就先把m对称

1.impossible：  
偶数个字符,遇到只出现一次的字符  
奇数个字符，遇到两个及以上的只出现一次的字符  
2.如果n是奇数，计算中间那个字符交换的次数的时候，不需要模拟把这个数移动到中间去，因为移动的步子是固定的

## 代码 ##

import java.util.Scanner;
    
    class Main { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		StringBuilder s = new StringBuilder(sc.next());
    		int count = 0;
    		int par = n - 1;
    		int flag = 0;
    		char temp;
    		for (int i = 0; i < par; i++) { 
    			for (int j = par; j >= i; j--) { 
    				if (j == i) { 
    					if (n % 2 == 0 || flag == 1) { 
    						System.out.println("Impossible");
    						return;
    					} else { 
    						flag = 1;
    						count += n / 2 - i;
    					}
    				} else if (s.charAt(i) == s.charAt(j)) { 
    					for (int k = j; k < par; k++) { 
    						temp = s.charAt(k);
    						s.setCharAt(k, s.charAt(k + 1));
    						s.setCharAt(k + 1, temp);
    						count++;
    					}
    					par--;
    					break;
    				}
    			}
    		}
    		System.out.println(count);
    		return;
    	}
    
    }