首页 > 代码库 > uva--10716Evil Straw Warts Live +回文串+贪心

uva--10716Evil Straw Warts Live +回文串+贪心

题意:

     输入一个字符串,我们可以交换这个字符串中的相邻字符;问至少经过多少步交换可以得到一个回文串;如果无论怎么交换都得不到回文串,输出“Impossible”;

思路:

   首先由回文串的定义和性质,可以得到两种不可能情况:1.当这个串长度为奇数时,如果出现次数为奇数次字母的数目不为1,则显然不可能。2.当这个串长度为偶数时,如果出现次数为奇数次字母的个数大于0,则不可能。

   除去这两种不可能的情况后,这个串就一定可以转成回文串。我们只需要考虑0--len/2(len为串长)的部分,对于第i个位置,我们需要的是str[i]==str[len-i-1],如果这两个位置的字符本来就相等,我们就考虑下一个位置;如果他们不相等,那么我们有两种策略:1.移动字符使得str[len-i-1]变成str[i];2.移动字符使得str[i]变成str[len-i-1]。具体选择那个,取决于那个的代价更小。由这种思路,我们可以写出代码。


代码如下:


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int check(char *str)
{
    int len=strlen(str);
    int cnt=0,a[30],i;
    memset(a,0,sizeof(a));
    for(i=0;i<len;i++)
       a[str[i]-'a']++;
    for(i=0;i<26;i++)
        if(a[i]%2)
             cnt++;
    if(len%2&&cnt!=1)
        return 0;
    if(len%2==0&&cnt!=0)
        return 0;
    return 1;
}

int main()
{
    int i,j,t,k;
    char str[110];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",str);
        if(!check(str))
        {
            printf("Impossible\n");
            continue;
        }
        int cnt=0;
        int len=strlen(str);
        for(i=0;i<len/2;i++)
        {
            if(str[i]==str[len-1-i])
                continue;
            else
            {
                for(j=i+1;j<len-i-1;j++)
                    if(str[j]==str[len-i-1])
                        break;
                for(k=len-i-2;k>i;k--)
                    if((str[k]==str[i]))
                        break;
                if(j-i<len-i-1-k)
                {
                    cnt+=j-i;
                    char ch=str[j];
                    for(k=j-1;k>=i;k--)
                        str[k+1]=str[k];
                    str[i]=ch;
                }
                else
                {
                    cnt+=len-i-1-k;
                    char ch=str[k];
                    for(j=k+1;j<=len-i-1;j++)
                        str[j-1]=str[j];
                    str[len-i-1]=ch;
                }
            }
        }
        printf("%d\n",cnt);
    }
  return 0;
}



uva--10716Evil Straw Warts Live +回文串+贪心