UVA 10716 Evil Straw Warts Live 回文数 贪心

题意：给出一串字符串，每次交换相邻的两个字符，求到达回文串的最少交换次数。

每次找最外面的两个字母，如果相同就向内缩进判断，如果不同，就找到里面能够让两边相同的最近的字符，进行交换，然后向内缩进判断。

调了挺久，以后一定要把算法搞清楚再敲。。。

代码：

 /*
 *   Author:        illuz <iilluzen[at]gmail.com>
 *   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 <cstdio>
#include <cstring>
#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;
}