1 #include <bits/stdc++.h> 2 using namespace std; 3 int num[26]; //存储每个字母出现的个数 4 int main() { 5 int n; 6 cin >> n; 7 string a; 8 cin >> a; 9 int flag = 0; //出现次数为奇数的字母的个数 10 int cnt = 0; //交换次数 11 int temp = n - 1; //字符串最后一个字母的下标 12 for(int i = 0; i < n; i++) { //遍历字符串,计算出现次数 13 num[a[i] - ‘a‘]++; 14 } 15 for(int i = 0; i < 26; i++) { //判断 16 if(num[i] % 2 != 0) { 17 flag++; 18 } 19 } 20 if ((n % 2 == 0 && flag >= 1) || (n % 2 == 1 && flag >= 2)) { 21 cout << "Impossible" << endl; 22 return 0; 23 } 24 for(int i = 0; i <= temp; i++) { 25 for(int j = temp; j >= i; j--) { 26 if(i >= j) { 27 cnt += n / 2 - i; 28 } else if(a[i] == a[j]) { 29 for(int k = j; k < temp; k++) { 30 swap(a[k], a[k + 1]); 31 cnt++; 32 } 33 temp--; 34 break; 35 } 36 } 37 } 38 cout << cnt << endl; 39 return 0; 40 }
原文:https://www.cnblogs.com/fx1998/p/12807094.html