Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 850 | Accepted: 239 |
Description
Input
Output
Sample Input
3 mamad asflkj aabb
Sample Output
3 Impossible 2
题目大意:给一个单词,为了让它变成一个回文串,允许相邻的两个数交换。求最少的交换次数,使得单词变成一个回文串。
解题思路:首先判断一下字母出现的奇数次的个数是否大于1, 大于1不满足。然后从左右开始遍历判断tmp[left] 和 tmp[right]是否相同,相同跳过, 不相同的话找到从左边开始第一个使得tmp[left + l] == tmp[right], 和从右边开始第一个使得tmp[left] == tmp[right + r]。比较l 和 r 的大小然后考虑该移动哪一边。
但是在这里我只用了temp[left]==temp[right-r],将所有的r求和即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
char arr[10000];
int b[28];
int solve()
{
int ans=0,len=strlen(arr),high=len-1;
for(int i=0;i<(len+1)/2-1;i++){
if(b[arr[i]-'a']>1){
for(int j=high;j>i;j--){
if(arr[i]==arr[j]){
for(int k=j+1;k<=high;k++){
arr[k-1]=arr[k];
ans++;
}
arr[high]=arr[i];
high--;
break;
}
}
b[arr[i]-'a']-=2;
}
else{
swap(arr[i],arr[i+1]);
ans++;
--i;
}
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
while(n--){
memset(b,0,sizeof(b));
scanf("%s",arr);
for(int i=0;arr[i];++i){
++b[arr[i]-'a'];
}
int cnt=0;
for(int i=0;i<27;i++){
if(b[i]%2) cnt++;
}
if(cnt>=2){
printf("Impossible\n");
continue;
}
else{
printf("%d\n",solve());
}
}
return 0;
}