uva 10716 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. Byswap we mean reversing the order of two adjacent symbols. For example, the string "mamad" may be transformed into the palindrome "madam" with 3 swaps:
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 Input3mamadasflkjaabbOutput for Sample Input3Impossible2
题目大意：给一段字符串，可以交换相邻的字符，问 要将他变成回文字符串，所要交换的最小次数。
解题思路：先判断字符串中数量为奇数的字母的个数是否大于1，若大于一，就“Imposiible”。然后从两头开始对比，若相同，，跳过；若不同，从右边往左找出第一个和左边的字符相同的字符，记录距离 l ， 再从左边往右边找出第一个和右边的字符相同的字符，记录距离 r ， 比较 l 和 r ，找出小的那一个， 进行替换。（说的不是太清楚，具体看代码）
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>using namespace std;int A[300];char B[105];int main() {int T;scanf("%d%*c", &T);while (T–) {char c;memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));int cnt = 0, cnt2 = 0;while (scanf("%c", &c), c != '\n') {A[c – 'a']++;if (A[c – 'a'] % 2) cnt2++;else cnt2–;B[cnt++] = c;}if (cnt2 > 1) {printf("Impossible\n");continue;}int len = strlen(B), ans = 0;for (int i = 0; i < len/ 2 + 1; i++) {int l = 0, r = 0;char temp;if (B[i] == B[len – i – 1])continue;else {for (int j = len – i – 1; j >= 0; j–) {if (B[i] != B[j]) {l++;}else break;}for (int j = i; j < len; j++) {if (B[len – i – 1] != B[j]) {r++;}else break;}if (l <= r) {temp = B[len – i – l – 1];for (int j = len – i – l – 1; j < len – i; j++) {B[j] = B[j + 1];}B[len – i] = temp;ans += l;}else {temp = B[i + r];for (int j = i + r; j > i; j–) {B[j] = B[j – 1];}B[i] = temp;ans += r;}}}printf("%d\n", ans);}return 0;}
看看花儿冲破北疆漫漫寒冬，妖娆绽放;
