1 #include <iostream> 2  3 using namespace std; 4  5 int main() 6 { 7     int n = 0; cin >> n; 8     char str[8001]; // 保存输入字符 9     int cnt[26] = { 0 }; // 字符计数10     for (int i = 0; i < n; ++i) {11         cin >> str[i];12         cnt[str[i] - ‘a‘] ++;13     }14 15     int odd = 0; // count odd num16     char charodd; // 奇数字符17     for (int i = 0; i < 26; ++i) {18         if (cnt[i] % 2 != 0) {19             odd++;20             charodd = i + ‘a‘;21         }22     }23     // 只能有一个奇数个的字符24     if (odd > 1) {25         cout << "impossible" << endl;26     }27     else {28         int change = 0;29 30         for (int i = 0; i < n / 2; ++i) {31             cout << "test" << endl;32             /* 33             当为奇数个数的字符时，找到其对称位置，然后从当前位置开始找到第一个和对称位置字符相同的字符，将其赋值到当前位置34             这样使得从开始位置到当前的i所有的位置都以完成回文匹配，不能直接将奇数的最后一个字符赋值到对称位置，因为之后还可能会有移位行为35             并无法确定当前移位完成后，其就确定在中间位置36             不能采用和偶数个数相同的方法37             */38             if (str[i] == charodd) {39                 int j = 0;40                 for (j = i; j <= n - i - 1; ++j)41                     if (str[j] == str[n - i - 1]) break;42                 change += j - i;43                 for (int k = i; k < j; ++k)44                     str[k + 1] = str[k];45                 str[i] = str[j];46             }47             /* 当为偶数个数的字符时，找到当前位置对称位置以左第一个（从对称位置开始）和当前位置相同的字符，并将其赋值到对称位置 */48             else {49                 int j = 0;50                 for (j = n - i - 1; j >= i; ++j)51                     if (str[j] == str[i]) break;52                 change += n - i - j - 1;53                 for (int k = j; k < n - i - 1; ++k)54                     str[k] = str[k + 1];55                 str[n - i - 1] = str[j];56             }57         }58 59         cout << "change = " << change << endl;60     }61 62     return 0;63 }