完美代價

問題描述

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

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

　　例如mamad

　　第一次交換 ad : mamda

　　第二次交換 md : madma

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

輸入格式

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

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

輸出格式

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

　　否則輸出Impossible

樣例輸入

5

mamad

樣例輸出

3

c代碼如下

總結

這道題一開始拿上手的時候，确實不知怎麼辦。而且說要用到貪心算法，但是我看了半天都不知道怎麼用到。但是我知道他肯定會有一種情況，輸出impossible，是以我就寫了一條語句，拿了10分。其實多找幾個例子，列出多種情況，然後自己解決，完了自己找規律，就發現其算法了。

知道算法了，就該編碼實作。這個時候，你就按照一種情況，一個流程走下去，一種情況的解決完了，就寫另外一種情況的程式。

程式寫完以後，就可以看程式，總結程式規律。總結出來調試，測試。ok，大功告成。