回文串，是一種特殊的字符串，它從左往右讀和從右往左讀是一樣的。小龍龍認(rèn)為回文串才是完美的。現(xiàn)在給你一個(gè)串，它不一定是回文的，請(qǐng)你計(jì)算最少的交換次數(shù)使得該串變成一個(gè)完美的回文串。

交換的定義是：交換兩個(gè)相鄰的字符

例如mamad

第一次交換 ad : mamda

第二次交換 md : madma

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

輸入格式:

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

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

輸出格式:

如果可能，輸出最少的交換次數(shù)。

否則輸出Impossible

輸入樣例:

5 mamad

輸出樣例:

3

這個(gè)題一開始是一點(diǎn)思路都沒有，后來聽了zx學(xué)長的證明后，就豁然開朗了，變成了一個(gè)簡(jiǎn)單模擬題，證明的話我不太會(huì)，光說結(jié)論吧：

假如有個(gè)回文串是這樣的：

AXXXXXAXX?

有一段字符串為上圖所示，我們現(xiàn)在需要匹配字母A，無論怎么匹配，步數(shù)都是2

我們可以這樣想，在上面的字符串中，紅色的X代表中間對(duì)稱點(diǎn)，那么將兩個(gè)A分別對(duì)稱過去，出現(xiàn)了兩個(gè)橙色的X，若想完成匹配，我們可以有好多種方案：

讓左邊的A向右交換兩次

讓右邊的A向右交換兩次

讓左邊的A向右交換一次，讓右邊的A向右交換一次

所以說交換兩次，是讓字母A達(dá)到匹配的最優(yōu)步數(shù)，若出現(xiàn)更多的交換次數(shù)，則一定不是最優(yōu)解

有了以上結(jié)論后，我們還需要處理的一個(gè)問題是，若A已經(jīng)完成匹配后，若后續(xù)再有字母在移動(dòng)的過程中涉及到了已經(jīng)完成匹配的字母A，字母A的位置也會(huì)發(fā)生變化，這時(shí)候該怎么處理呢？

這個(gè)問題就比較簡(jiǎn)單了，可以從兩端開始處理，每處理完最外層的字母后，將區(qū)間向里收縮，再重復(fù)上述步驟進(jìn)行匹配即可，這樣可以保證我們的操作無后效性，即不會(huì)影響前面的所有操作

還有一個(gè)小細(xì)節(jié)，就是如何判斷能否通過上述操作最后形成回文串，其實(shí)我們?cè)谝婚_始記錄一下每個(gè)字母出現(xiàn)的次數(shù)，必須保證奇數(shù)次字母最多有1個(gè)，否則肯定無法組成回文串，那么現(xiàn)在問題來了，我們又可以分兩種情況來討論：

若回文串中沒有奇數(shù)次的字母

若回文串中有奇數(shù)次的字母

第一種情況很簡(jiǎn)單，就是上述討論的情況，針對(duì)第二種情況，顯而易見該字符串的長度一定是奇數(shù)，并且組成的回文串最中間一定是該字母，這樣一來，我們?cè)谔幚淼臅r(shí)候，有兩種方法

忽略掉這個(gè)落單的字母不管，因?yàn)樽詈笕羲械淖帜付继幚硗戤吅?#xff0c;該字母一定會(huì)回到最中間的位置上，所以其貢獻(xiàn)的步數(shù)為0

特殊處理這個(gè)落單的字母，單獨(dú)計(jì)算其貢獻(xiàn)，為了防止在后續(xù)會(huì)重復(fù)計(jì)算，我們?cè)谔幚硗暝撟帜钢?#xff0c;不予模擬，也就是說計(jì)算完貢獻(xiàn)后假裝將其刪除

然后就上代碼了，兩份代碼都能A：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #define Pi acos(-1.0) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100; int n;string s;int cnt[30];int cal(char ch) {int ans=0;for(int i=0;i<n/2;i++){if(s[i]==ch)//若遇到奇數(shù)次字母{if(cnt[ch-'a']==1)//若奇數(shù)次字母落單了{(lán)reverse(s.begin(),s.end());//翻轉(zhuǎn)字符串i--;//記得讓光標(biāo)回溯一個(gè)單位continue;//然后繼續(xù)處理即可}else//沒落單的話，實(shí)時(shí)更新還剩多少個(gè)字母cnt[ch-'a']-=2;}int cnt=0;for(int j=n-i-1;j>i;j--){if(s[i]==s[j]){ans+=cnt;while(cnt)//小模擬{swap(s[n-i-1-cnt],s[n-i-1-cnt+1]);cnt--;} break;}cnt++;}}return ans; }int main() { // freopen("input.txt","r",stdin);cin>>n>>s;for(int i=0;i<n;i++)cnt[s[i]-'a']++;int num=0;char ch='A';for(int i=0;i<26;i++)if(cnt[i]&1){num++;ch='a'+i;}if(num>1)printf("Impossible\n");else{printf("%d\n",cal(ch));}return 0; } #include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #define Pi acos(-1.0) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100; int n;string s;int cnt[30];int cal() {int ans=0;//剩余字母的貢獻(xiàn)int ans2=0;//落單字母的貢獻(xiàn)int temp=n;for(int i=0;i<n/2;i++){int j;int cnt=0;for(j=temp-1;j>i;j--){if(s[i]==s[j]){ ans+=cnt;while(cnt){swap(s[temp-1-cnt],s[temp-1-cnt+1]);cnt--;}temp--; break;}cnt++;}if(i==j)//若當(dāng)前字母沒有找到匹配的對(duì)象，則說明該字母為落單字母ans2=(n-1)/2-i;//計(jì)算落單字母的貢獻(xiàn)，計(jì)算完貢獻(xiàn)后并不會(huì)將其模擬到中間點(diǎn)，而是將其直接忽略，避免重復(fù)計(jì)算}return ans+ans2; }int main() { // freopen("input.txt","r",stdin);cin>>n>>s;for(int i=0;i<n;i++)cnt[s[i]-'a']++;int num=0;for(int i=0;i<26;i++)if(cnt[i]&1)num++;if(num>1)printf("Impossible\n");else{printf("%d\n",cal());}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯 - 完美的代价(贪心+模拟)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。