UVA 10716 Evil Straw Warts Live(貪心）

Problem D: Evil Straw Warts Live
A palindrome is a string of symbols that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string "mamad" may be transformed into the palindrome "madam" with 3 swaps:
swap "ad" to yield "mamda"
swap "md" to yield "madma"
swap "ma" to yield "madam"

The first line of input gives n, the number of test cases. For each test case, one line of input follows, containing a string of up to 100 lowercase letters. Output consists of one line per test case. This line will contain the number of swaps, or "Impossible" if it is not possible to transform the input to a palindrome.

Sample Input
3
mamad
asflkj
aabb
Output for Sample Input
3
Impossible
2題意：給定一些字符串，要求出能否通過交換字母變換為回文。。如果可以輸出最少變換次數。。

思路:貪心。。

1、先判斷能不能變換為回文。。如果字符串中沒有或只有1個字母是奇數。就可以組成。。

2、每次從第一個字母開始。從後往前找到一個相同字母。放到最後就是匹配了。。每次移動的次數為當前位置到最後的位置的距離。

要注意有單個字母為奇數的情況。。最後要把這個字母另外拿出來移到最中間。。一開始沒考慮這個wa了- -

代碼:

#include <stdio.h>
#include <string.h>

int t, len, sum, judge, end, vis[30], mark[105];
char sb[105], v;

void Init() {
    sum = 0;
    judge = 1;
    memset(vis, 0, sizeof(vis));
    memset(mark, 0, sizeof(mark));
    gets(sb);
    len = strlen(sb);
    end = len - 1;
}

void Judge() {//判斷能不能組成回文
    int bo = 0;
    for (int i = 0; i < len; i ++)
	vis[sb[i] - 'a'] ++;
    for (int i = 0; i < 26; i ++) {
	if (vis[i] % 2) {
	    bo ++;
	    if (bo == 2) {
		judge = 0;
		break;
	    }
	    v = i + 'a';
	}
    }
}

void solve() {//變換
    for (int i = 0; i < len / 2; i ++) {
	int j;
	for (j = end; j >= i + 1; j --)
	    if (sb[j] == sb[i]) {
		mark[i] = 1;
		sum += end - j;
		for (int k = j; k < end; k ++)
		    sb[k] = sb[k + 1];
		end --;
		break;
	    }
    }
    if (len % 2) {//奇數情況
	for (int i = 0; i < len; i ++)
	   if (sb[i] == v && mark[i] == 0) {
	       sum += len / 2 - i;
	       break;
	   } 
    }
    if (judge)
	printf("%d\n", sum);
    else
	printf("Impossible\n");
}
int main() {
    scanf("%d%*c", &t);
    while (t --) {
	Init();
	Judge();
	solve();
    }
    return 0;
}