codeforces 600C Make Palindrome

要保证变化次数最少就是出现次数为奇数的相互转化，而且对应字母只改变一次。保证字典序小就是字典序大的字母变成字典序小的字母。

长度n为偶数时候，次数为奇数的有偶数个，按照上面说的搞就好了。

n为奇数时，要考虑最后中间那个字母。交换法可以证明，其实是贪心最后没有转化掉的字母。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int LEN = 2e5+5;
char s[LEN];

int cnt[26];

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    gets(s);
    int i = 0, j;
    for(; s[i]; i++){
        cnt[s[i]-'a']++;
    }
    int n = i;
    i = 0; j = 26;
    while(i < j){
        if((cnt[i]&1) && (cnt[j]&1)) cnt[i++]++,cnt[j--]--;
        else {
            if(cnt[i]&1^1) i++;
            if(cnt[j]&1^1) j--;
        }
    }
    int md = -1;
    if(n&1)  md = i;
    j = 0;
    for(i = 0; i < 26; i++){
        cnt[i] >>= 1;
        while(cnt[i]--){
            s[j++] = i+'a';
        }
    }
    if(n&1){
        s[j++] = md+'a'; s[j] = 0;
        printf("%s",s);
        for(i = j-2; i >= 0; i--) putchar(s[i]);
    }
    else {
        s[j] = 0;
        printf("%s",s);
        for(i = j-1; i >= 0; i--) putchar(s[i]);
    }
    puts("");
    return 0;
}