基礎練習 完美的代價

問題：

問題描述

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

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

例如mamad

第一次交換 ad : mamda

第二次交換 md : madma

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

輸入格式

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

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

輸出格式

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

否則輸出Impossible

樣例輸入

5

mamad

樣例輸出

3

需要了解：

這道題的關鍵字是貪心算法，去百度了一下貪心算法，簡單來說就是在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

在本題中也就是找到能夠與之相匹配的字符。然后，進行交換，直至達到目標要求。

題目分析：

首先分析Impossible 的兩種情況

n為奇數時，如果已經有一個字符出現的次數為奇數，還找到了一個字符出現的次數為奇數，那么就不能構成回文串。

n為偶數時，只要找到有一個字符出現的次數為奇數，那么就不能構成回文串。

還有一個就是題目所說的最小的交換次數

如果 n 為偶數，那么從第一字符開始，從后往前找第一個和它相同的字符，如果找了，就將找到的字符交換到最后一個位置，在下一次遍歷時，就可以不用管剛才已經交換好的那來兩個字符，下一次從第二個字符開始，從倒數第二個字符開始遍歷，執行和上述相同的操作。

如果 n 為奇數，在字符串的某一個位置找到了那個出現次數為奇數的字符，我們不必將次字符現在就交換到中間位置，而是先計算它到中間位置需要交換的次數，然后累加到 count 中，將剩下的字符都交換到對稱后，再交換這個字符即可。

這是因為如果把奇數移動到中間，假設有一對數都在以中間為界限的左邊或者都在右邊的話，那么交換成回文的時候就一定要經過中間，這就會造成count多增加了一次，這是不必要的，因為可以所有的回文移動完了之后再把這個獨立的奇數移動過去，不僅能達到同樣的效果還能保證交換次數最少。

例如：

有這么幾個數

b d c c f f b

我們不考慮第二個奇數直接交換第三個數，這樣只需要1步，但是當你把第二個奇數交換到中間之后就會有如下結果

b c c d f f b

可以了解一下 φ(>ω

代碼：

#include

#include

using namespace std;

int main() {

int n;

cin >> n;

string s;

cin >> s;

int end = n - 1;//字符串最后一個字符

int count = 0;//交換次數

int OddNum = 0;//判斷是否已經有一個單獨的奇個數的字符了

for (int i = 0; i < end; ++i) {//從第一個字符到倒數第二個字符遍歷

for (int j = end; j >= i; --j) {//從最后一個開始，到第i個字符，尋找與s[i]相同的字符

if (i == j) {//如果沒找到

if (n % 2 == 0 || OddNum == 1) { //不可能的兩種情況

cout << "Impossible" << endl;

return 0;

}

OddNum = 1;//找到一個字符出現的次數為奇數

count += n / 2 - i;//將次字符交換到中間位置的次數

}

else if (s[i] == s[j]) {//如果找到了，將s[j]交換到s[end]位置

for (int k = j; k < end; ++k) {

swap(s[k], s[k + 1]);//交換相鄰兩個位置的字符

++count;

}

--end;//末尾遞減

break; //開始從i+1處重復操作

}

}

}

cout << count << endl;

system("pause");

return 0;

}

對于我：

但是在這里我還發現我有一個基礎知識點薄弱的地方那就是多個if跟if··· if else 的區別

if (條件){語句}

這種格式中，程序會依次判斷條件1和條件2是否成立并根據結果決定是否執行語句1和語句2，也就是說，第一個 if 塊和第二個 if 塊沒有影響(除非在執行第一個 if 塊的時候就兇殘地 return 了)

而下面這種格式，

if (條件){}

else if(條件){}

f 塊和 else if 塊本質上是互斥的！也就是說，一旦語句1得到了執行，程序會跳過 else if 塊，else if 塊中的判斷語句以及語句2一定會被跳過；同時語句2的執行也暗含了條件1判斷失敗和語句1沒有執行；當然還有第3個情況，就是條件1和條件2都判斷失敗，語句1和語句2都沒有得到執行。

總結

以上是生活随笔為你收集整理的完美的代价 c语言,蓝桥杯基础练习 完美的代价的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。