蓝桥杯2020年国赛C/C++C组第7题 重复字符串(思维与贪心)

 解题思路：首先明确，若能将S变为一个K次字符串，那么它的长度应该是K的倍数，如果不是，那么就无法将S变为一个K次字符串，直接按题目要求输出-1即可，如果是，就开始遍历(S/K)长度的字符串它的每一个字符，而既然是一个K次字符串，那么这个(S/K)长度的字符串它的每一个字符应该出现K次，而这个字符串每一个字符的修改都是互不影响的，即我们可以通过贪心策略，在每一个字符的K次遍历中，把字符修改成出现最多的那一个字符，那么修改次数即为每一个字符中的最少情况，我们将(S/K)字符串中的所有字符的修改次数进行统计，完成输出即可

#include<stdio.h>
#include<string.h> 
int max(int a,int b)
{
 return a>=b?a:b;//定义一个返回两者之间较大值的函数
}
int main()
{
 const int N=1e5+10;
  char s[N];//定义一个足以满足题目字符串输入长度的字符数组
  int k;
  int count[26]={0};//统计a到z的出现次数
  int sum=0;
  int i,j; 
  scanf("%d",&k);
  getchar();//吞掉换行符，防止对后续输入造成影响
  gets(s);
  if(strlen(s)%k!=0) printf("-1");//如果字符串S长度不为K的倍数(余数不为0) 输出-1
  else
  {
   int n=strlen(s)/k;//计算拆分成K次后的小字符串的长度
   for(i=0;i<n;i++)//遍历小字符串的每一个字符
   {
    for(j=0;j<26;j++) count[j]=0;//每一次遍历时，将count数组初始化为0，代表a到z还未曾出现
    int ma=0;//统计出现最多的次数
    for(j=0;j<k;j++)//把K次出现过的字符全部找出来
    {
     char x=s[i+j*n];//把当前遍历的这个字符存储进一个字符变量
     count[x-'a']++;//这个字符每出现一次，就统计一次
     ma=max(ma,count[x-'a']);//更新出现最多的字符它的出现次数
    }
    sum+=k-ma;//将不是出现的最多的字符都改为出现最多的字符，就完成了每一次的修改最少情况
   }
   printf("%d",sum);//遍历完小字符串的所有字符，那么修改次数之和便是整个字符串需要的最小修改次数
  }                 //完成输出
  return 0;
}

原文地址：https://blog.csdn.net/2403_88254028/article/details/145157325

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！