完美的代价

简介: 完美的代价

     

问题描述

  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。

  交换的定义是:交换两个相邻的字符

  例如mamad

  第一次交换 ad : mamda

  第二次交换 md : madma

  第三次交换 ma : madam (回文!完美!)

输入格式

  第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)

  第二行是一个字符串,长度为N.只包含小写字母

输出格式

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

  否则输出Impossible

样例输入

5

mamad

样例输出

这道题采用贪心做法,贪心的原理是,既然是移动,只要每个位置上的字符对应就好,所有只要从从结尾开始,往前查找,找到一个与从前往后开始的位置的字符相等,就将该字符往后移动,让后就是从倒数第二个字符开始,知道完全排好序。

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int end = n - 1;    //字符串最后一个字符
    int cnt = 0;        //交换次数
    int oddNum = 0;        //判断是否已经有一个单独的奇个数的字符了
    for (int i = 0; i < end; i++)//从第一个字符到倒数第二个字符遍历
    {
        for (int j = end; j >= i; j--)//从最后一个开始,到第i个字符,寻找与s[i]相同的字符
        {
            if (i == j)       //如果没找到
            {
                if (n % 2 == 0 || oddNum == 1)  //不可能的两种情况 偶数且找到至少一个只出现的字符,奇数且找到至少两个只出现一次的字符
                {
                    cout << "Impossible";
                    return 0;
                }
                oddNum = 1;            //找到一个字符出现的次数为奇数
                cnt += n / 2 - i;    //将次字符交换到中间位置的次数
            }
            else if (s[i] == s[j])    //如果找到了,将s[j]交换到s[end]位置
            {
                for (int k = j; k < end; k++)    //交换相邻两个位置的字符
                {
                    swap(s[k], s[k+1]);
                    cnt++;
                }
                end--;                //末尾递减
                break;                //开始从i+1处重复操作
            }
        }
    }
    cout << cnt;
    return 0;
}


相关文章
|
算法 测试技术 C++
C++算法:让数组不相等的最小总代价
C++算法:让数组不相等的最小总代价
多大数量级会出现哈希碰撞
写作目的 今天在网上看到一个有意思的问题是多大的数据量会出现哈希碰撞?我当时的想法是2的32次方,因此hascode是init类型的,哈哈。 还是可以写个demo实验一下的。真实答案是10W5K左右的量级会出现哈希碰撞
258 0
多大数量级会出现哈希碰撞
|
SQL 关系型数据库 MySQL
Mysql索引降维 优化查询 提高效率
数据的选择度越大,则维度越大。 降维,按我个人的理解是:在大量的数据中,一层一层地筛选过滤,维度也会逐渐减低。 点线面中,共有黑红两种颜色。 目标:筛选出所有红色的点 步骤:选出所有带有红色点的面 –> 选出所有带有红色点的线 –> 在线上选出所有红色点
123 0
|
存储 缓存 关系型数据库
怎么减少行锁对性能的影响
怎么减少行锁对性能的影响
145 0
怎么减少行锁对性能的影响
|
存储 监控 关系型数据库
分分钟解决MySQL查询速度慢与性能差
分分钟解决MySQL查询速度慢与性能差 一、什么影响了数据库查询速度 1.1 影响数据库查询速度的四个因素 1.2 风险分析 QPS: QueriesPerSecond意思是“每秒查询率”,是一台服务器每秒能够相应的查询次数,是对一个特定的查询服务器在规定时间内所处理流量多少的衡量标准。
2786 0
多线程的优点和代价
多线程优点/代价
1282 0