讨论/算法和数据结构/一道蓝桥杯的算法题,有没有会做的大佬/
一道蓝桥杯的算法题,有没有会做的大佬

题目描述

回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
  交换的定义是:交换两个相邻的字符
  例如mamad
  第一次交换 ad : mamda
  第二次交换 md : madma
  第三次交换 ma : madam (回文!完美!)

输入格式

第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
  第二行是一个字符串,长度为N.只包含小写字母

输出格式

如果可能,输出最少的交换次数。
  否则输出Impossible

样例输入

5
mamad

样例输出

3

题目的主要意思:通过相邻字符的交换形成回文串,求最小交换次数

不要太在意输入和输出的形式,只要求核心算法就行。
网上找的解答都没有详细解析,希望大佬可以帮助我。

共 5 个回复

这篇文章很详细了

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int l;
    scanf("%d",&l);
    char a[l];
    //清除一个无效字符---回车
    getchar();
    //输入字符串a
    gets(a);
    //数组b的26个变量分别对应26个字母
    int b[26]={0},i;
    //统计字符串中各字母出现的次数
    for(i=0;i<l;i++)
    {
        b[a[i]-'a']++;
    }
    //统计出现次数为奇数的字母个数
    int k=0;
    for(i=0;i<26;i++)
    {
        if(b[i]%2!=0)
            k++;
    }
    //若存在2个及以上次数为奇数的字母
    if(k>=2)
    {
        printf("Impossible");
        exit(0);
    }
    else
    {
        //h计形成回文所需次数,
        //m计奇数字符串时,奇数字母到达中点位置所需次数
        //g用于改变交换位置长度
        int h=0,g=l,m=0;
        for(i=0;i<(l+1)/2;i++)
        {
            int j;
            //查找是否存在不同位置的相同字母
            for(j=g-1;j>i;j--)
            {
                //存在
                if(a[i]==a[j])
                {
                    while(j<g-1)
                    {
                        //交换至对应位置
                        char t;
                        t=a[j];
                        a[j]=a[j+1];
                        a[j+1]=t;
                        j++;
                        h++;//记录次数
                    }
                    g--;
                    break;
                }
            }
            //不存在,则为奇数字母
            if(j==i)
                m=(l-1)/2-i;
        }
        printf("%d",h+m);
    }
    return 0;
}

https://blog.csdn.net/qq_40605470/article/details/79268979

5

交换是只可以相邻的元素交换吗?

看不懂题

感觉是dp ,你可以试试

贪心应该可以