蓝桥杯 基础训练 完美的代价--------------C语言—菜鸟级
C语言 完美 蓝桥 菜鸟 代价
2023-06-13 09:13:12 时间
/*问题描述 回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。 小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的, 请你计算最少的交换次数使得该串变成一个完美的回文串。 交换的定义是:交换两个相邻的字符 例如mamad 第一次交换 ad : mamda 第二次交换 md : madma 第三次交换 ma : madam (回文!完美!) 输入格式 第一行是一个整数N,表示接下来的字符串的长度(N <= 8000) 第二行是一个字符串,长度为N.只包含小写字母 输出格式 如果可能,输出最少的交换次数。 否则输出Impossible 样例输入 5 mamad 样例输出 3 思路: 用贪心,先保证能构 成回文 由两边向中间查找找 注意边界情况 和特殊情况;
*/
#include<stdio.h>
#include <string.h>
int main()
{
char a[8005];//存储字符串
char b[8005];//用于判断字符串能否构成字符串;
long long i,j,len,t=1,t1=0,sum=0;
scanf("%lld\n",&len);
for(i=0;i<len;i++)
{scanf("%c",&a[i]);
b[i]=a[i];
}
for(i=0;i<len-1;i++)
for(j=i+1;j<len;j++)
if(b[i]>b[j]){char c=b[i];b[i]=b[j];b[j]=c;}//按ASCII 值排序便于统计
for(i=0;i<len;i++)
if(b[i]==b[i+1]&&i<len){t++;}//统计每个相同字符的数量
else //用于判断字符串能否构成字符串;
{ if(t%2==1)t1++;//若字符数量为奇数 且为奇数字符的种类大于等于2则不能构成回文
if(t1>=2)break;
t=1; }
if(t1>=2)printf("Impossible\n");
else
{ i=0;//从第一位字符(0位)寻找对应字符;第一位对应最后一位 因此需找到与之匹配的字符换到最后一位
for(j=len-1;j>i;j--)//为次数最小则就近原则 从后向前查找遇到的第一个匹配字符则通过相邻字符交换
{ for(t=j;t>i;t--)//到对应位置 从匹配字符位到与查找对应位置根据交换原则,交换后两个交换位置
if(a[t]==a[i])//之间 的字符循序不变 可视为移位插入法(i 对应位置 是j 匹配字符 是t;则从t交换
{sum+=j-t;//到j 则需 j-t 次;
b[0]=a[t];
while(t<j)
{a[t]=a[t+1];t++;} //移位
a[j]=b[0];i++;break;//匹配字符插入对应位 然后i++寻找下一位
}
if(t==i&&j!=i){j++;char c=a[i];a[i]=a[i+1];a[i+1]=c;sum++;}//若查找的对应字符为中心(奇数)字符
// 且不是查找 中心(奇数)字符 的对应位
} // 则先将 中心(奇数)字符与非中心字符交换重找此对应位
printf("%lld\n",sum);
}
return 0;
}
相关文章
- 八大排序算法(C语言实现)
- 基本图形Linux C语言实现基本图形的精彩绘制(linuxc语言打印)
- C语言fmod()函数:求x/y的余数(针对浮点数)
- MySQL C语言开发入门指南(mysqlc类)
- 编译在Linux系统中编译C语言源代码(linux下c源代码)
- MySQL编译:数据库C语言支持的完美解决方案(cmysql编译)
- 开源世界C语言MySQL的互联之旅(c mysql开源)
- C语言与Oracle的完美结合(c 配oracle)
- MySQL数据库快速开发与C语言的完美结合(c mysql sql)
- C语言与Oracle数据库的完美结合(c add oracle)
- 关于C语言除0引发的思考
- C语言位图算法详解