首页 > 代码库 > 贪心基础入门讲解一——完美字符串
贪心基础入门讲解一——完美字符串
约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。
约翰不在乎字母大小写。（也就是说字母F和f）的完美度相同。给定一个字符串，输出它的最大可能的完美度。例如：dad，你可以将26分配给d，25分配给a，这样整个字符串完美度为77。
分析： 由排序不等式，出现次数最多的字母显然应该给26。所以这个题目变成了统计每种字母出现的次数了，然后按照出现次数从大到小，依次分配从高到低的权值。这就是最朴素的贪心思想。
输入
输入一个字符串S(S的长度 <= 10000)，S中没有除字母外的其他字符。输出
由你将1-26分配给不同的字母，使得字符串S的完美度最大，输出这个完美度。输入示例
dad输出示例
77
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;char a[10100];int b[30],ans;int main(){ cin>>a; for(int i=0;i<=strlen(a);i++) { if(a[i]==‘a‘||a[i]==‘A‘) b[1]++; if(a[i]==‘b‘||a[i]==‘B‘) b[2]++; if(a[i]==‘c‘||a[i]==‘C‘) b[3]++; if(a[i]==‘d‘||a[i]==‘D‘) b[4]++; if(a[i]==‘e‘||a[i]==‘E‘) b[5]++; if(a[i]==‘f‘||a[i]==‘F‘) b[6]++; if(a[i]==‘g‘||a[i]==‘G‘) b[7]++; if(a[i]==‘h‘||a[i]==‘H‘) b[8]++; if(a[i]==‘i‘||a[i]==‘I‘) b[9]++; if(a[i]==‘j‘||a[i]==‘J‘) b[10]++; if(a[i]==‘k‘||a[i]==‘K‘) b[11]++; if(a[i]==‘l‘||a[i]==‘L‘) b[12]++; if(a[i]==‘m‘||a[i]==‘M‘) b[13]++; if(a[i]==‘n‘||a[i]==‘N‘) b[14]++; if(a[i]==‘o‘||a[i]==‘O‘) b[15]++; if(a[i]==‘p‘||a[i]==‘P‘) b[16]++; if(a[i]==‘q‘||a[i]==‘Q‘) b[17]++; if(a[i]==‘r‘||a[i]==‘R‘) b[18]++; if(a[i]==‘s‘||a[i]==‘S‘) b[19]++; if(a[i]==‘t‘||a[i]==‘T‘) b[20]++; if(a[i]==‘u‘||a[i]==‘U‘) b[21]++; if(a[i]==‘v‘||a[i]==‘V‘) b[22]++; if(a[i]==‘w‘||a[i]==‘W‘) b[23]++; if(a[i]==‘x‘||a[i]==‘X‘) b[24]++; if(a[i]==‘y‘||a[i]==‘Y‘) b[25]++; if(a[i]==‘z‘||a[i]==‘Z‘) b[26]++; } sort(b+1,b+27); int k=26,d=26; while(k){ if(b[d]!=0){ ans+=b[d]*k; k--; d--; } else break; } cout<<ans; }
如果对你有所帮助，别忘了加好评哦；么么哒！！下次见！88
贪心基础入门讲解一——完美字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。