蓝桥杯 完美的代价

时间:2023-02-14 08:12:26

题目描述

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

输入格式

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

输出

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

样例输入

5
mamad

样例输出

3

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 int main()
 6 {
 7     int n,i,j,k,f,p,r,w,res=0;
 8     char s[8005];
 9     cin>>n;
10     cin>>s;
11     f=0;
12     for(i=0,j=n-1; i<j; i++,j--)
13     {
14             p=-1;
15         for(r=j;r>i;r--)
16         {
17             if(s[r]==s[i])
18             {
19                 for(w=r;w<j;w++)
20                 s[w]=s[w+1];
21                 p=j-r;      
22                 break;
23             }
24         }
25         if(p==-1)
26         {
27             if(n%2==1 && !f)
28             {
29                 f=1;
30                 res=res+n/2-i;
31                 j++;
32             }
33             else
34             {
35                 res=-1;
36                 break;
37             }
38         }
39         else
40          res=res+p;
41     }
42     if(res==-1)
43     printf("Impossible\n");
44     else
45     printf("%d\n",res);
46     return 0;
47 }