Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 728 | Accepted: 198 |
Description
Input
Output
Sample Input
3 mamad asflkj aabb
Sample Output
3 Impossible 2
题目的大概意思是让你判断输入的字符串是否能变为回文数,若不能,则输出Impossible,若能,则输出从该字符串变为回文串所需要的最少的步数,(一次只能交换相邻的两个数)。
如何判断该串能否变为回文串:题中已经说明,输入的字符串中只有小写的字母,所以统计各个字母出现的频率,若出现两个或以上的字母频率为奇数,则该字符串,不可能变为回文串。
怎么找出最少的步数:这里用到了贪心的思想。具体看代码。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 8010
int n,ans;
char arr[maxn];
int b[27];
void solve();
int main()
{
scanf("%d",&n);
while(n--){
memset(b,0,sizeof(b));
scanf("%s",arr);
int cnt = 0;
ans = 0;
for(int i = 0 ; arr[i];i++){
b[arr[i] - 'a'] ++;
}
for(int i = 0; i < 27;i++){
if(b[i] % 2 == 1){
cnt ++;
}
}
if(cnt >= 2){
printf("Impossible\n");
continue;
}
solve();
printf("%d\n",ans);
}
return 0;
}
void solve(){
int len = strlen(arr);
int high = len - 1;
for(int i = 0; i < (len+1)/ 2 - 1;i++){
if(b[arr[i] - 'a'] % 2 == 0 || b[arr[i] - 'a'] > 1){
for(int j = high; j > i; j--){
if(arr[j] == arr[i]){
char tmp = arr[j];
for(int k = j + 1; k <= high; k++){
arr[k-1] = arr[k];
ans++;
}
arr[high] = tmp;
high --;
break;
}
}
b[arr[i] - 'a'] -= 2;
}
else{
swap(arr[i],arr[i+1]);
i--;
ans ++;
}
}
}