藍橋杯 完美的代價 【貪心】

問題描述

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

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

　　例如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
*/