蓝桥杯基础训练完美的代价

本文主要是介绍蓝桥杯基础训练完美的代价，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思想：

运用了贪心的思想 从字符串的左面和右面开始匹配 保证了第一次到的相同字符距离左面的最近，然后将字符串的左面和右面字符去掉 匹配剩余的 一直进行下去 就会产生最终结果!

代码

#include<cstdio>
const int maxn = 8001; 
char str[maxn];
int parse(int len)//
{int py;int ans1 = 0;int ans=0;int r = len-1;//A（）是否非法：：：非法就退出：非法条件串是有偶数字符则不能有独立字符 2串有奇数字符则只能有一个独立字符//这里我们设置两个士兵 放在字符串左面和右面 左面的士兵不动右面的士兵在他所在的位置插一个旗子然后从右    面向左走 如果发现字符相同就计算他和旗子的距离然后加到结果变量中  如果与左面士兵重合了还没有找到 那么就要进行判断 A()如果没有退出说明这可能是唯一的一个独立字符 就要计算出他和中间位置的距离 在最后移动到中间（这样会避免重复移动） 第一次使得第一个字符和最后一个字符形成了回文 然后右面的士兵将他的旗子向左移动一个位置然后他站在了旗子的位置 进行下一波匹配！for(int i=0;i<r;i++)//mamad{for(int j = r;j>=i;j--){if(j==i){ans++;if(ans>1||len%2==0)return -1;py = len/2-i;break;}else if(str[i]==str[j]){ans1+=r-j;for(int k=j;k<r;k++)str[k] = str[k+1];//str[r] = str[i];r--;break;}}}return ans1+py;
}
int main()
{int n;scanf("%d",&n);scanf("%s",str);int ans=parse(n);if(ans==-1){printf("Impossible\n");}else{printf("%d\n",ans);}return 0;}