蓝桥杯 完美的代价 贪心

? 基础练习 完美的代价 ?
时间限制：1.0s ? 内存限制：512.0MB
? ?
问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)
输入格式
　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母
输出格式
　　如果可能，输出最少的交换次数。
　　否则输出Impossible
样例输入
5
mamad
样例输出
3

思路：贪心，至于这样为什么是正确的(不知道，具体看代码

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=0;
    bool flag=false;//前面存不存在一个单身汉
    for(int i=0,j=n-1;i<j;++i){//枚举每一个没有找到配偶的字符
        for(int k=j;k>=i;k--){//为它找配偶
            if(i==k){//找到自己了，说明是单身汉,在一个字符串里，若是偶数个则不能有单身汉，若是奇数个只能有一个单身汉
                if(n%2==0||flag){
                    cout<<"Impossible"<<endl;
                    return 0;
                }
                flag=true;
                ans+=n/2-i;//这里先把单身汉放在这里，若是把它先移到中间，其他人找配偶时，就可能会经过他，这是会有多余操作(把他从中间让道，再把他放中间)
            }
            else if(s[i]==s[k]){//找到之后放到相应的位置
                for(int l=k;l<j;++l){
                    swap(s[l],s[l+1]);
                    ans++;
                }
                j--;//匹配下一个
                break;//找到之后就跳出循环，不用找第三者了
            }
            
        }
    }
    cout<<ans<<endl;
    return 0;
}

蓝桥杯 完美的代价 贪心

原文：https://www.cnblogs.com/clear-love/p/11290690.html