藍橋杯 BASIC-19 基礎練習 完美的代價

NO IMAGE

問題描述
迴文串,是一種特殊的字串,它從左往右讀和從右往左讀是一樣的。小龍龍認為迴文串才是完美的。現在給你一個串,它不一定是迴文的,請你計算最少的交換次數使得該串變成一個完美的迴文串。
交換的定義是:交換兩個相鄰的字元
例如mamad
第一次交換 ad : mamda
第二次交換 md : madma
第三次交換 ma : madam (迴文!完美!)
輸入格式
第一行是一個整數N,表示接下來的字串的長度(N <= 8000)
第二行是一個字串,長度為N.只包含小寫字母
輸出格式
如果可能,輸出最少的交換次數。
否則輸出Impossible
樣例輸入
5
mamad
樣例輸出
3
分析:過程見程式碼註釋部分。其中有兩個注意點:
1.impossible的情況:如果有一個字元出現的次數是奇數次數,而且n是偶數,那麼不可能構成迴文
如果n是奇數,但是已經有一個字元出現的次數是奇數次數了,那麼如果又有一個字元是奇數次數,就不可能構成迴文。
2.如果n是奇數,計算中間那個字元交換的次數的時候,不需要模擬把這個數移動到中間去,因為移動到中間的話假設有一對數都在左邊或者都在右邊,
那麼交換成迴文的時候就要經過中間,就會每次把cnt多加了1,而這個1是沒有必要的,因為可以所有的迴文移動完了之後再把這個獨立的奇數移動過去,才能保證交換次數最少。

#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int j = n - 1;
int cnt = 0;//cnt用來統計交換的次數
int flag = 0;//flag判斷是否已經有一個單獨的奇個數的字元了
for(int i = 0; i < j; i  ) {//i指標從頭遍歷到倒數第二個字元
for(int k = j; k >= i; k--) {//k指標從後面往前一直到i尋找和s[i]相同的s[k]
if(k == i) {//如果找不到相同的
if(n % 2 == 0 || flag == 1) {//impossible的兩種情況
cout << "Impossible";
return 0;
}
flag = 1;
cnt  = n / 2 - i;
} else if(s[k] == s[i]) {
for(int l = k; l < j; l  ) {
swap(s[l], s[l 1]);//把s[k]換到s[j]處
cnt  ;//統計交換次數
}
j--;
break;
}
}
}
cout << cnt;
return 0;
}