BASIC-19_蓝桥杯_完美的代价

思路(贪心):

1.两边往中间逼近,步数少;

2.单个字符出现时只考虑移动到中间的步数,不做移动,因为这是最后进行,不影响结果;

示例代码:

#include <stdio.h>
#define N 8000

int main(void)
{
  int n = 0 ;
  int i = 0 , j = 0 , k = 0 , flag = 0 , sign = 0 , sum = 0;
  char arr[N] ;

  scanf("%d",&n);
  scanf("%s",arr);

  k = n - 1 ; /*对称位置*/
  for (i = 0 ; i <= k ; i ++)
  {
    for (j = k ; j >= i ; j --)
    {

      /*出现单个字符*/
      if (i == j)
      {

        if (n%2 == 0 || sign)
        {
          flag ++;   /*第一次出现忽略*/ 
          break;
        }
        sign ++;   
        sum += n/2 - i;
        break;
      }

      /*匹配到的回文*/
      if (arr[i] == arr[j])
      {
        sum += k - j;
        while (j != k)
        {
          arr[j] = arr[j+1];
          j ++;
        }
        arr[j] = arr[i];
        k --;
        break;
      }
    }
    if (flag)
    {
      break;
    }
  }
  if (flag)
  {
    printf("Impossible");
  }
  else
  {
    printf("%d",sum);
  }

  return 0;
}

上一篇:小程序多端框架全面测评:chameleon、Taro、uni-app、mpvue、WePY


下一篇:golang web框架 beego 学习 (二) router and controller