基礎練習 完美的代價（貪心）

Description

回文串，是一種特殊的字元串，它從左往右讀和從右往左讀是一樣的。小龍龍認為回文串才是完美的。現在給你一個串，它不一定是回文的，請你計算最少的交換次數使得該串變成一個完美的回文串。

交換的定義是：交換兩個相鄰的字元

例如mamad

第一次交換 ad : mamda

第二次交換 md : madma

第三次交換 ma : madam (回文！完美！)

Input

第一行是一個整數N，表示接下來的字元串的長度(N <= 8000)

第二行是一個字元串，長度為N.隻包含小寫字母

Output

如果可能，輸出最少的交換次數。

否則輸出Impossible

Sample Input 1

5

mamad

Sample Output 1

3

Hint

HINT:時間限制：1.0s 記憶體限制：512.0MB

Source

藍橋杯練習系統 ID: 60 原題連結: http://lx.lanqiao.cn/problem.page?gpid=T60

思路：從左邊起依次掃描，每記錄一個字母，從右向左尋找最近的與它相同的字母，移動到回文對稱的位置，記錄步數。

Impossible的情況：

1.如果n為偶數，有1個字元出現奇數次，不會構成回文。

2.如果n為奇數，有2個或以上的字元出現奇數次，不會構成回文串。

需要注意的是，如果n為奇數，最後移動中間那個字元，這樣移動次數最少。

AC代碼

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	char str[8000];
	int i, j, k;
	for (i = 0; i < n; i++) {
		cin >> str[i];
	}
		
	int m = n-1;	
	int flag = 0, ans = 0;
	for (i = 0; i < m; i++) {	//從前向後周遊，到N-1結束 
		for (j = m; j >= i; j--) {	//N開始從後向前周遊找與str[i]相同的字元 
			if (i == j) { 	//沒有找到相同的字元 
				flag++;
				if (n % 2 == 0 || flag > 1) {
					cout << "Impossible" << endl;
					return 0;
				}
				ans += n / 2 - i;	//最後移動中間那個字元，直接加上次數
				break;
			} else if (str[i] == str[j]) {	//找到相同的字元 
				for (k = j; k < m; k++) {	//交換并且記下次數 
					swap(str[k], str[k + 1]);
					ans++;
				}
				m--;	
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
} 
           

如果有錯誤歡迎大家指出~