天天看點

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

問題描述

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

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

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

繼續閱讀