题目大意:给一个字符串,判断是否能通过交换字母构成回文,如果能,计算所需的最小交换次数。

  如果字符串中出现奇数次的字母的个数>1,则不能构成回文。然后...就没思路了...看网上说用贪心的思想先从两端开始考虑,决定两端的字母后再缩小问题范围直至字符串长度<=2。可是看网上的代码都是只考虑了两端字母,而没有考虑其他可能的情况,如mdcfamcda,如果两端都变为m的话需要交换3次,两端都变为a的话需要交换4次,可是如果变为d的话只需要交换两次,但是网上的代码没考虑这种情况竟然AC了,为什么?是测试数据的问题还是其中有什么我没看出来的东西?

 #include <cstdio>
#include <cstring> int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int T;
scanf("%d", &T);
char str[];
while (T--)
{
scanf("%s", str);
int cnt[] = {};
for (int i = ; str[i] != '\0'; i++)
cnt[str[i]-'a']++;
int t = ;
for (int i = ; i < ; i++)
if (cnt[i] % ) t++;
if (t > )
{
printf("Impossible\n");
continue;
}
int ans = ;
for (int s = , e = strlen(str)-; s < e; s++, e--)
{
if (str[s] != str[e])
{
int p = s;
while (str[p] != str[e]) p++;
int q = e;
while (str[q] != str[s]) q--;
if (p - s < e - q)
{
ans += p-s;
for (int i = p; i > s; i--)
str[i] = str[i-];
}
else
{
ans += e-q;
for (int i = q; i < e; i++)
str[i] = str[i+];
}
}
}
printf("%d\n", ans);
}
return ;
}
05-11 18:12