贪心算法,本质是局部最优解生成全局最优解。
但是不要忘记要先进行排序,否则可能无法得到全局最优解
#include<stdio.h>
#include<string.h>
int main(void)
{
int num;
scanf("%d",&num);
char str[10000]={0};
while(scanf("%s",&str)!=EOF)
{
int len=strlen(str);
int times[26]={0};
for(int i=0;i<len;i++)
{
int temp=str[i]-'a';
times[temp]++;
}
//降序排序
for(int i=0;i<25;i++)
{
for(int j=0;j<25-i;j++)
{
if(times[j]<times[j+1])
{
int t;
t=times[j+1];
times[j+1]=times[j];
times[j]=t;
}
}
}
//for(int i=0;i<26;i++){printf("%d",times[i]);}
int ini=26;
int sum=0;
for(int i=0;i<26;i++)
{
if(times[i]!=0)
{
sum+=times[i]*ini;
ini--;
}
}
printf("%d\n",sum);
}
return 0;
}

京公网安备 11010502036488号