問題描述
回文串,是一種特殊的字元串,它從左往右讀和從右往左讀是一樣的。小龍龍認為回文串才是完美的。現在給你一個串,它不一定是回文的,請你計算最少的交換次數使得該串變成一個完美的回文串。
交換的定義是:交換兩個相鄰的字元
例如mamad
第一次交換 ad : mamda
第二次交換 md : madma
第三次交換 ma : madam (回文!完美!)
輸入格式
第一行是一個整數N,表示接下來的字元串的長度(N <= 8000)
第二行是一個字元串,長度為N.隻包含小寫字母
輸出格式
如果可能,輸出最少的交換次數。
否則輸出Impossible
樣例輸入
5
mamad
樣例輸出
3
解題思路
假如字元串所含字元個數為奇數,則有且隻有一種字元的個數為奇數;為偶數則不能存在出現次數為奇數的字元。
調整交換:
從最左邊到n/2枚舉每個字元,從要處理的字元串的最右邊開始往左找,找到相同的字元則交換到對應的位置,同時+交換次數。
如果找不到,則這個字元為處在字元串(奇數)最中間位置的字元,需要先假想不存在這個字元,當其他所有字元調整完之後再把它移到中間,+交換次數。
AC代碼
#include <iostream>
using namespace std;
void Swap(char &t1,char &t2)
{
char c = t2;
t2 = t1;
t1 = c;
}
int main()
{
int n;
char ch[8005];
cin >> n >> ch;
int ans=0;
bool flag1=false,flag2=false; // flag2用于确定出現次數為奇數的字元是否為0
int r=n-1;
for(int i=0;i<=n/2;i++) {
for(int j=r;j>=i;j--) { // 從右往左找與ch[i]相同的數
if(i == j) { // 沒有找到與ch[i]相同的
if(n%2 == 0 || flag2) { // 一共偶數個字元 || 已經有出現次數為奇數的字元
cout << "Impossible\n";
flag1 = true;
}
else {
flag2 = true;
ans += n/2-i; // 移到中間所需步數
}
break;
}
if(ch[i] == ch[j]) { //找到相同的
for(int k=j;k<r;k++)
Swap(ch[k],ch[k+1]); //移到對應位置
ans += (r-j);
r--; // 位置已經比對好的不再參與之後的調整
break;
}
}
if(flag1)
break;
}
if(!flag1)
cout << ans << endl;
}
/*
9
ffdejjell
14
*/