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

/问题描述
　　回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。
小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，
请你计算最少的交换次数使得该串变成一个完美的回文串。
　　交换的定义是：交换两个相邻的字符
　　例如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];
  }

   <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token number">-1</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
 <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
   <span class="token keyword">if</span><span class="token punctuation">(</span>b<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">&gt;</span>b<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span><span class="token keyword">char</span> c<span class="token operator">=</span>b<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>b<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>b<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>b<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>c<span class="token punctuation">;</span><span class="token punctuation">}</span><span class="token comment" spellcheck="true">//&#x6309;ASCII &#x503C;&#x6392;&#x5E8F;&#x4FBF;&#x4E8E;&#x7EDF;&#x8BA1; </span>

   <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> 
     <span class="token keyword">if</span><span class="token punctuation">(</span>b<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span>b<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">&amp;&amp;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">)</span><span class="token punctuation">{</span>t<span class="token operator">++</span><span class="token punctuation">;</span><span class="token punctuation">}</span><span class="token comment" spellcheck="true">//&#x7EDF;&#x8BA1;&#x6BCF;&#x4E2A;&#x76F8;&#x540C;&#x5B57;&#x7B26;&#x7684;&#x6570;&#x91CF; </span>
     <span class="token keyword">else</span>                         <span class="token comment" spellcheck="true">//&#x7528;&#x4E8E;&#x5224;&#x65AD;&#x5B57;&#x7B26;&#x4E32;&#x80FD;&#x5426;&#x6784;&#x6210;&#x5B57;&#x7B26;&#x4E32;&#xFF1B;</span>
     <span class="token punctuation">{</span> <span class="token keyword">if</span><span class="token punctuation">(</span>t<span class="token operator">%</span><span class="token number">2</span><span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span>t1<span class="token operator">++</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x82E5;&#x5B57;&#x7B26;&#x6570;&#x91CF;&#x4E3A;&#x5947;&#x6570; &#x4E14;&#x4E3A;&#x5947;&#x6570;&#x5B57;&#x7B26;&#x7684;&#x79CD;&#x7C7B;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;2&#x5219;&#x4E0D;&#x80FD;&#x6784;&#x6210;&#x56DE;&#x6587; </span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>t1<span class="token operator">&gt;=</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token keyword">break</span><span class="token punctuation">;</span>
          t<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span>
     <span class="token keyword">if</span><span class="token punctuation">(</span>t1<span class="token operator">&gt;=</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;Impossible\n&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     <span class="token keyword">else</span>
     <span class="token punctuation">{</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x4ECE;&#x7B2C;&#x4E00;&#x4F4D;&#x5B57;&#x7B26;&#xFF08;0&#x4F4D;&#xFF09;&#x5BFB;&#x627E;&#x5BF9;&#x5E94;&#x5B57;&#x7B26;&#xFF1B;&#x7B2C;&#x4E00;&#x4F4D;&#x5BF9;&#x5E94;&#x6700;&#x540E;&#x4E00;&#x4F4D; &#x56E0;&#x6B64;&#x9700;&#x627E;&#x5230;&#x4E0E;&#x4E4B;&#x5339;&#x914D;&#x7684;&#x5B57;&#x7B26;&#x6362;&#x5230;&#x6700;&#x540E;&#x4E00;&#x4F4D; </span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span>len<span class="token number">-1</span><span class="token punctuation">;</span>j<span class="token operator">&gt;</span>i<span class="token punctuation">;</span>j<span class="token operator">--</span><span class="token punctuation">)</span><span class="token comment" spellcheck="true">//&#x4E3A;&#x6B21;&#x6570;&#x6700;&#x5C0F;&#x5219;&#x5C31;&#x8FD1;&#x539F;&#x5219; &#x4ECE;&#x540E;&#x5411;&#x524D;&#x67E5;&#x627E;&#x9047;&#x5230;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x5339;&#x914D;&#x5B57;&#x7B26;&#x5219;&#x901A;&#x8FC7;&#x76F8;&#x90BB;&#x5B57;&#x7B26;&#x4EA4;&#x6362; </span>
        <span class="token punctuation">{</span> <span class="token keyword">for</span><span class="token punctuation">(</span>t<span class="token operator">=</span>j<span class="token punctuation">;</span>t<span class="token operator">&gt;</span>i<span class="token punctuation">;</span>t<span class="token operator">--</span><span class="token punctuation">)</span><span class="token comment" spellcheck="true">//&#x5230;&#x5BF9;&#x5E94;&#x4F4D;&#x7F6E; &#x4ECE;&#x5339;&#x914D;&#x5B57;&#x7B26;&#x4F4D;&#x5230;&#x4E0E;&#x67E5;&#x627E;&#x5BF9;&#x5E94;&#x4F4D;&#x7F6E;&#x6839;&#x636E;&#x4EA4;&#x6362;&#x539F;&#x5219;&#xFF0C;&#x4EA4;&#x6362;&#x540E;&#x4E24;&#x4E2A;&#x4EA4;&#x6362;&#x4F4D;&#x7F6E; </span>
          <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>t<span class="token punctuation">]</span><span class="token operator">==</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token comment" spellcheck="true">//&#x4E4B;&#x95F4; &#x7684;&#x5B57;&#x7B26;&#x5FAA;&#x5E8F;&#x4E0D;&#x53D8; &#x53EF;&#x89C6;&#x4E3A;&#x79FB;&#x4F4D;&#x63D2;&#x5165;&#x6CD5;&#xFF08;i &#x5BF9;&#x5E94;&#x4F4D;&#x7F6E; &#x662F;j &#x5339;&#x914D;&#x5B57;&#x7B26; &#x662F;t;&#x5219;&#x4ECE;t&#x4EA4;&#x6362; </span>
          <span class="token punctuation">{</span>sum<span class="token operator">+</span><span class="token operator">=</span>j<span class="token operator">-</span>t<span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x5230;j &#x5219;&#x9700; j-t &#x6B21;&#xFF1B; </span>
          b<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>a<span class="token punctuation">[</span>t<span class="token punctuation">]</span><span class="token punctuation">;</span>
          <span class="token keyword">while</span><span class="token punctuation">(</span>t<span class="token operator">&lt;</span>j<span class="token punctuation">)</span>
          <span class="token punctuation">{</span>a<span class="token punctuation">[</span>t<span class="token punctuation">]</span><span class="token operator">=</span>a<span class="token punctuation">[</span>t<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>t<span class="token operator">++</span><span class="token punctuation">;</span><span class="token punctuation">}</span>  <span class="token comment" spellcheck="true">//&#x79FB;&#x4F4D; </span>
            a<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>b<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">;</span><span class="token keyword">break</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x5339;&#x914D;&#x5B57;&#x7B26;&#x63D2;&#x5165;&#x5BF9;&#x5E94;&#x4F4D; &#x7136;&#x540E;i++&#x5BFB;&#x627E;&#x4E0B;&#x4E00;&#x4F4D; </span>
          <span class="token punctuation">}</span>
          <span class="token keyword">if</span><span class="token punctuation">(</span>t<span class="token operator">==</span>i<span class="token operator">&amp;&amp;</span>j<span class="token operator">!=</span>i<span class="token punctuation">)</span><span class="token punctuation">{</span>j<span class="token operator">++</span><span class="token punctuation">;</span><span class="token keyword">char</span> c<span class="token operator">=</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>a<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>a<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>c<span class="token punctuation">;</span>sum<span class="token operator">++</span><span class="token punctuation">;</span><span class="token punctuation">}</span><span class="token comment" spellcheck="true">//&#x82E5;&#x67E5;&#x627E;&#x7684;&#x5BF9;&#x5E94;&#x5B57;&#x7B26;&#x4E3A;&#x4E2D;&#x5FC3;&#xFF08;&#x5947;&#x6570;&#xFF09;&#x5B57;&#x7B26; </span>
                                                                    <span class="token comment" spellcheck="true">// &#x4E14;&#x4E0D;&#x662F;&#x67E5;&#x627E; &#x4E2D;&#x5FC3;&#xFF08;&#x5947;&#x6570;&#xFF09;&#x5B57;&#x7B26; &#x7684;&#x5BF9;&#x5E94;&#x4F4D; </span>
        <span class="token punctuation">}</span>                                                           <span class="token comment" spellcheck="true">// &#x5219;&#x5148;&#x5C06; &#x4E2D;&#x5FC3;&#xFF08;&#x5947;&#x6570;&#xFF09;&#x5B57;&#x7B26;&#x4E0E;&#x975E;&#x4E2D;&#x5FC3;&#x5B57;&#x7B26;&#x4EA4;&#x6362;&#x91CD;&#x627E;&#x6B64;&#x5BF9;&#x5E94;&#x4F4D; </span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%lld\n&quot;</span><span class="token punctuation">,</span>sum<span class="token punctuation">)</span><span class="token punctuation">;</span>

 <span class="token punctuation">}</span>
return 0;
}