试题 基础练习 完美的代价

 

 

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define maxn 8005
 4 int mp[30];
 5 int main(){
 6     int N,sum=0,k,c=0,i,j,flag=0,flag1=0;
 7     string s;
 8     cin>>N;
 9     cin>>s;
10     memset(mp,0,sizeof(mp));
11     //判断字符串能否成为回文串 
12     for(int i=0;i<N;i++){
13         mp[s[i]-'a']++;
14     } 
15     for(int i=0;i<24;i++){
16         if(mp[i]%2==1)    flag1++;
17         if(flag1>1)    break;
18     } 
19     if(flag1>1) printf("Impossible\n");
20     else{
21     int temp=N-1;
22     for(i=0;i<temp;i++){//从前向后找 
23         for(j=temp;j>i;j--){//从后向前找 
24             if(s[i]==s[j]){//遇到相等的字母则需要交换到合适的地方
25              //从j位置移动到与i对称的位置(即temp)
26              for(k=j;k<temp;k++){
27                  s[k]=s[k+1];
28              } 
29             s[temp]=s[i];//也即之前的s[j],但s[j]已经被其他字母占了,所以用与它值相等的s[i]表示 
30             sum+=temp-j;//这次移动的次数
31             temp--;//缩小边界
32             break; 
33             }
34         }
35         if(j==i){//也即之前的“从后向前找”找不到相等的字母,只有自身,则将它移动到中间,并且标记 
36             if(N%2==1&&c==0){
37                 sum+=(N/2 - i);
38                 c==1;
39             }
40             cout<<"j:"<<i<<" i: "<<temp<<endl; 
41         }
42     }
43     cout<<sum<<endl;
44     }
45 }

 

上一篇:LightOJ - 1422——(区间DP)


下一篇:2020.3.2考试 子串 AC自动机+高斯消元