蓝桥杯 试题 基础练习 完美的代价（贪心算法详解）

问题描述

　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)

输入格式

　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

　　如果可能，输出最少的交换次数。
　　否则输出Impossible

样例输入

5
mamad

样例输出

3

解题思路：

求最值问题，90%都是贪心。

贪心算法的三步走！

第一步

明确到底什么是最优解？

------------>字符串通过有限的交换变成回文串，最小的交换次数 。

第二步

明确什么是子问题的最优解？

------------>把字符串中的一个字母使得相对字符串对称的位置出现同样的字母，最小的交换次数。

第三步

分别求出子问题的最优解再堆叠出全局最优解。

这样分析，思路就很清晰了，先判断是否能成为回文串，统计字符串每个字母的数量，如果有超过一个奇数，肯定不是回文串。

然后就是解决子问题：从第一个字母开始，从后往前找，找到与其相同的字母，交换到对应的位置，如果找不到，就交换到中间位置。子问题解决了，也就解决了整个问题。

我写的代码用了很多string的类函数，我简单的介绍一下：

.size():返回字符串的长度

.erase(index，Len):删除下标包括index之后的Len个字符

.find(string):在字符串中寻找string，如果找不到就返回-1，找到了就返回第一个字符的位置。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<string>
#include<cmath>
using namespace std;
int main(){
  int n;
  int a[30]={0};
  cin>>n;
  string str;
  cin>>str;
  for(int i=0;i<str.length();i++)  
    a[str[i]-'a']++;
  int cnt=0;
  for(int i=0;i<30;i++)
    if(a[i]%2)
      cnt++;
  if(cnt>1)
    cout<<"Impossible"<<endl;
  else{
    int ans=0;
    while(str.size()>1)
    {
      string first;
      first+=str[0];
      str.erase(0,1);//删除第一个字母 
      if(str.find(first)==-1)//在字符串中找和第一个字母相同的字母，-1表示没找到 
        ans+=str.size()/2;//交换到中间的代价               
      else//如何找到了，就删除那个字母的位置，计算其代价 
      {
        string s(str.rbegin(),str.rend()); 
        int w=s.find(first);//寻找第一个字母的位置 
        ans+=w;
        str.erase(str.size()-w-1,1);
      }       
    }
    cout<<ans<<endl;
  }

}