|
题意：给出一串字符串，每次交换相邻的两个字符，求到达回文串的最少交换次数。
每次找最外面的两个字母，如果相同就向内缩进判断，如果不同，就找到里面能够让两边相同的最近的字符，进行交换，然后向内缩进判断。
调了挺久，以后一定要把算法搞清楚再敲。。。
代码：
/*
* Author: illuz
* Blog: http://blog.csdn.net/hcbbt
* File: uva10716.cpp
* Lauguage: C/C++
* Create Date: 2013-09-03 23:03:20
* Descripton: UVA 10716 Evil Straw Warts Live, greed
*/
#include
#include
#define rep(i, n) for (int i = 0; i < (n); i++)
#define swap(a, b) {int t = a; a = b; b = t;}
#define mc(a) memset(a, 0, sizeof(a))
const int MAXN = 110;
int n, len, app[26], cnt;
char s[MAXN];
void solve(char* a, int l) {
if (a[0] == a[l - 1]) return;
for (int i = 1; i < l - 1; i++)
if (a[i] == a[l - 1]) {
for (int j = i; j > 0; j--)
swap(a[j], a[j - 1]);
cnt += i;
return;
}
else if (a[l - i - 1] == a[0]) {
for (int j = l - i - 1; j < l - 1; j++)
swap(a[j], a[j + 1]);
cnt += i;
return;
}
}
int main() {
scanf("%d", &n);
while (n--) {
scanf("%s", s);
len = strlen(s);
mc(app);
rep(i, len) app[s[i] - 'a']++;
cnt = 0;
rep(i, 26) if (app[i] % 2) cnt++;
if (cnt > 1)
printf("Impossible\n");
else {
cnt = 0;
rep(i, len / 2)
solve(s + i, len - 2 * i);
printf("%d\n", cnt);
}
}
return 0;
}
|