1/22テスト1(STLシミュレーション欲張り)E.(欲張りはアルファベットの修正と順序の調整によって文字列を回文列にする)Make Palindrome

1/22テスト1(STLシミュレーション欲張り)

E.(アルファベットの修正と順序の調整で文字列を回文列にする)Make Palindrome

A string is called palindrome if it reads the same from left to right and from right to left. For example “kazak”, “oo”, “r” and “mikhailrubinchikkihcniburliahkim” are palindroms, but strings “abb” and “ij” are not. You are given string s consisting of lowercase Latin letters. At once you can choose any position in the string and change letter in that position to any other lowercase letter. So after each changing the length of the string doesn’t change. At first you can change some letters in s. Then you can permute the order of letters as you want. Permutation doesn’t count as changes. You should obtain palindrome with the minimal number of changes. If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. So firstly you should minimize the number of changes and then minimize the palindrome lexicographically. Input The only line contains string s (1 ≤ |s| ≤ 2·105) consisting of only lowercase Latin letters. Output Print the lexicographically smallest palindrome that can be obtained with the minimal number of changes. Example Input aabc Output abba Input aabcd Output abcba
題意:文字列で、アルファベットの種類と順序を変えることで文字列を回文列にすることができ、アルファベットの種類を変更して変更回数として記録し、順序を調整して記録しないで、回文列を出力することができます.複数の調整方式があれば、辞書順が最小となる場合を出力する.
構想:num配列で各アルファベットの出現回数を記録し、アルファベットaから遍歴し、アルファベットの数が偶数であれば、彼を首尾に1つずつ置き、アルファベットの数が奇数であれば、彼を別のアルファベットに修正する必要があることを説明し、あるいは別のアルファベットを彼に修正する必要がある.ここで私たちは辞書の順序を最小にするために、大アルファベットを小アルファベットに変更すべきだ.ここではaから遍歴しているからだ.では、zから前を巡り、奇数の数のアルファベットを見つけて、現在のアルファベットに変更すればいいだけです.特に考慮しなければならないのは、文字列が奇数であれば、単一の文字が真ん中に置かれ、これは追加の考慮が必要である.PS:間違いやすい!!!後ろから前へ回るときは、現在の要素を超えてはいけないと判断条件に注意しなければなりません.例えばaabccは、aaaを並べてbを並べたとき、後から遍歴して奇数のアルファベットが見つからず、その時に置いても中心に達していない場合がありますが、この場合は奇数のアルファベットを中間位置に置くべきです.すなわちacbcaは、このように処理しないとabcbaになり、2回アルファベットが変わります.

#include 
#include 
#include 
#include 
#define MAXN 200005

using namespace std;

int main()
{
    int num[30] = {0};
    char s[MAXN], ans[MAXN];
    scanf("%s", s);
    int len = strlen(s);
    for(int i = 0; i < len; i++)
    {
        num[s[i] - 'a']++;
    }
    int l = 0;
    for(int i = 0; i < 26; i++)
    {
        if(num[i])
        {
            int k = num[i] / 2;
            while(k--)
            {
                ans[l] = 'a' + i;
                ans[len - 1 - l] = 'a' + i;
                l++;
                num[i] -= 2;
            }
            if(num[i] == 1)
            {
                if((len % 2) && (l == len / 2))
                {
                    ans[l] = 'a' + i;
                    num[i]--;
                }
                else
                {
                    int j = 25;
                    while(num[j] % 2 == 0 && j > i)
                        j--;
                    if(j > i)
                    {
                        num[j]--;
                        ans[l] = 'a' + i;
                        ans[len - l - 1] = 'a' + i;
                        num[i]--;
                        l++;
                    }
                    else
                    {
                        ans[len/2] = 'a' + i;
                        num[i]--;
                    }
                }
            }
        }
    }
    ans[len] = '\0';
    printf("%s
", ans);
    return 0;
}