题目大意：给一个字符串，判断是否能通过交换字母构成回文，如果能，计算所需的最小交换次数。
如果字符串中出现奇数次的字母的个数>1，则不能构成回文。然后...就没思路了...看网上说用贪心的思想先从两端开始考虑，决定两端的字母后再缩小问题范围直至字符串长度<=2。可是看网上的代码都是只考虑了两端字母，而没有考虑其他可能的情况，如mdcfamcda，如果两端都变为m的话需要交换3次，两端都变为a的话需要交换4次，可是如果变为d的话只需要交换两次，但是网上的代码没考虑这种情况竟然AC了，为什么？是测试数据的问题还是其中有什么我没看出来的东西？
1 #include <cstdio> 2 #include <cstring> 3 4 int main() 5 { 6 #ifdef LOCAL 7 freopen("in", "r", stdin); 8 #endif 9 int T; 10 scanf("%d", &T); 11 char str[110]; 12 while (T--) 13 { 14 scanf("%s", str); 15 int cnt[30] = {0}; 16 for (int i = 0; str[i] != ' '; i++) 17 cnt[str[i]-'a']++; 18 int t = 0; 19 for (int i = 0; i < 26; i++) 20 if (cnt[i] % 2) t++; 21 if (t > 1) 22 { 23 printf("Impossible "); 24 continue; 25 } 26 int ans = 0; 27 for (int s = 0, e = strlen(str)-1; s < e; s++, e--) 28 { 29 if (str[s] != str[e]) 30 { 31 int p = s; 32 while (str[p] != str[e]) p++; 33 int q = e; 34 while (str[q] != str[s]) q--; 35 if (p - s < e - q) 36 { 37 ans += p-s; 38 for (int i = p; i > s; i--) 39 str[i] = str[i-1]; 40 } 41 else 42 { 43 ans += e-q; 44 for (int i = q; i < e; i++) 45 str[i] = str[i+1]; 46 } 47 } 48 } 49 printf("%d ", ans); 50 } 51 return 0; 52 }