蓝桥杯--完美的代价

http://47.104.209.207/problem/old1061

可以证明直接将头部的字母固定，而后从尾部找与其相同的字母并不会使结果变差。

对于第i个字母，假设与之匹配的为k，他应该放置的位置是n-i-1，那么ans=k-(n-i-1)

如果第i个字母放于其他的位置上，对于第i个字母对，ans并不会变差，而且可能会使得其他的变差。

需要注意的是如果长度为奇数，是可以容许一个不匹配的字母的。

#include<cmath>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,res=0;
    string s;
    cin>>n>>s;
    bool flag=false;
    for(int i=0,j=n-1;i<j;i++){
        for(int k=j;k>=i;k--){
            if(k==i){//意思就是没找到
                if(n%2==0||flag){
                    cout<<"Impossible"<<endl;
                    return 0;
                }
                flag=true;
                res+=n/2-i;
            }else if(s[k]==s[i]){//如果找到了
                for(int l=k;l<j;l++){
                    swap(s[l],s[l+1]);
                    res++;
                }
                j--;
                break;
            }
        }
    }
    cout<<res;
    return 0;
}