基础练习 完美的代价  
时间限制:1.0s   内存限制:512.0MB
      
锦囊1
  使用贪心算法。
锦囊2
  从左到右枚举每个字符,移动对应字符。个数为单的字符放中间。
 
问题描述
  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
  交换的定义是:交换两个相邻的字符
  例如mamad
  第一次交换 ad : mamda
  第二次交换 md : madma
  第三次交换 ma : madam (回文!完美!)
输入格式
  第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
  第二行是一个字符串,长度为N.只包含小写字母
输出格式
  如果可能,输出最少的交换次数。
  否则输出Impossible
样例输入
5
mamad
样例输出
3
 
 /*
完美的代价:通过交换相邻字符,使原字符串化为回文字符串 。
*/
#include<stdio.h>
#include<stdlib.h>
int main(){
int i,j,l,n,k,sum=,flat=,c=-;
char *a;
scanf("%d",&n);
a=(char *)malloc(n*sizeof(char));
scanf("%s",a);
j=n-;
//利用贪心的思想,将每个遍历的字符找到后面与他相同的然后交换到正确的位置时所需的交换次数
for(i=;i<j;i++){
for(k=j;k>=i;k--){
if(k==i){//说明没有找到与a[i]相同的字符
if(n%==||c!=-){//如果n为偶数或者a[i]不是唯一一个单个无相同字符
flat=;
break;
}
c=;//n为奇数,将第一个单个的字符a[i]移到中间位置所需的交换次数
sum=sum+n/-i;
break;
}
if(a[k]==a[i]){
for(l=k;l<j;l++){
a[l]=a[l+];
}
a[j]=a[i];
sum=sum+j-k;
j--;
break;
}
}
if(flat==){
break;
}
}
if(flat==)
printf("Impossible");
else if(sum==)
printf("");
else
printf("%d\n",sum);
return ;
}

最新文章

  1. 用Powershell启用Windows Azure上的远程桌面服务
  2. Linux(centeros)下安装jdk
  3. python 实时遍历日志文件
  4. ThreadPool线程池 小结
  5. 深入ThreadLocal之一
  6. Codeforces Round #192 (Div. 1) A. Purification 贪心
  7. ExtJS练手
  8. Android抓包方法
  9. react学习笔记-01
  10. 项目Beta冲刺Day3
  11. 搭建Hexo博客(四)-设置
  12. python之迭代器、生成器与面向过程编程
  13. Window离线环境下如何安装pyhanlp
  14. U3D学习06-数学基础
  15. CentOS 6.5下Redis安装测试
  16. 数据库设计 Step by Step (1)——扬帆启航
  17. Unity-------------------------关于GUI绘制的编程
  18. jquery ajax中 php前台后台文件中编辑都是uft-8,返回数据还是乱码
  19. python 2 类与对象
  20. 功率谱密度(PDS)的MATLAB分析

热门文章

  1. js 动态增加行删除行
  2. Java面试基础部分合集
  3. Java虚拟机学习 - JDK可视化监控工具 ( 7 )
  4. js Circle类
  5. Response.Flush() Response.End()的区别
  6. Python学习笔记010——形参与实参
  7. RHCE7 -- systemctl命令
  8. tcp流协议产生的粘包问题和解决方案
  9. python AES双向对称加密解密
  10. 理解:Before和:After伪元素