提示说是用贪心算法，求大神教

问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如mamad
　　第一次交换 ad : mamda
　　第二次交换 md : madma
　　第三次交换 ma : madam (回文！完美！)
输入格式
　　第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母
输出格式
　　如果可能，输出最少的交换次数。
　　否则输出Impossible
样例输入
5
mamad
样例输出
3

感觉这题有难度，不明白贪心算法。做个标记。

我也来做个标记~

我也做个标记。
希望大神解决。

关注中

上网一查，贪心算法是做出对眼下最优方案的调整，即不考虑长远得利，感觉与象棋博弈思路正好相反。但本题的“眼前最优”该如何考虑还是得不出个所以然。

基本能实现最优就要想了

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
bool Check(char* p)
{
    char* pHead = p;
    char* pTail = p+strlen(p) - 1;
    while(*(pHead++) == *(pTail--))
    {
        if(pHead == pTail || (pHead + 1) == pTail)
        {
            return true;
        }
    }
    return false;
}

bool CheckChange(char* p)
{
    int a[100][2] = {0};
    char* pTmp = p;
    char c = '0';
    int n = 0;
    while(*pTmp)
    {
        for(int i = 0; i < 100; i++)
        {
                if(a[i][0] == 0)
                {
                    a[i][0] = *pTmp;
                    a[i][1] = 1;
                    break;
                }else if(a[i][0] == *pTmp)
                {
                    a[i][1]++;
                    break;
                }
        }
  


        pTmp++;
    }

    for(int i = 0; i < 100; i++)
    {
        if(a[i][0] == 0)
        {
            break;
        }
        if(a[i][1]%2 != 0)
        {
            n++;
        }
    }
    if(n >= 2)
    {
        return true;
    }
    else

    {
        return false;
    }
}

int main()
{
    char* pIn = (char*)malloc(9000);
    memset(pIn, '\0', sizeof(pIn));
    scanf("%s", pIn);
    int n = 0;
    char* p1 = pIn+strlen(pIn)-1;
    char* p2 = pIn+strlen(pIn)-2;
    char c = '0';
    int t = 0;
    if(Check(pIn))
    {
        printf("%d\n", n);
        return 0;
    }
    else if(CheckChange(pIn))
    {
        printf("Impossible\n");
        return 0;
    }
    while(1)
    {
            n++;
            c = *p1;
            *p1 = *p2;
            *p2 = c;
            if(Check(pIn))
            {
                printf("%d\n", n);
                break;
            }

            if(p2 == (pIn+t))
            {
                 p1 = pIn+strlen(pIn)-(1+t);
                 p2 = pIn+strlen(pIn)-(2+t);
            }
            else
            {
                p1--;
                p2--;
            }
            if(*(pIn+t) == *(pIn+strlen(pIn)-(1+t)))
            {
                 t++;
                 p1 = pIn+strlen(pIn)-(1+t);
                 p2 = pIn+strlen(pIn)-(2+t);
            }
    }
    printf("转换后:%s\n", pIn);
    free(pIn);
    return 0;
}

[此贴子已经被作者于2017-3-23 00:58编辑过]

这样可否？
1、先确定给定的串是否可组成回文串，如果是奇数串，只有其中一个字符的个数是奇数，其余都是偶数。
2、首尾指针逐步向中间移，如果是回文串就返回。
3、另一指针从尾指针前向首指针搜寻与首指针相同的字符。
.......找得到就与尾指针交换字符，首尾指针移动。（因交换规则要求，要向后滚动交换相邻的字符）
.......找不到就与首指针交换字符，首尾指针不移动。
4、继续到2、

[此贴子已经被作者于2017-3-23 14:34编辑过]

这个方法交换字符不一定相邻~好像不符合题意耶~

真没认真看，原来交换要求是相邻的，那就滚过去。

[此贴子已经被作者于2017-3-23 00:03编辑过]