1182 完美字符串

题目来源： Facebook Hacker Cup选拔

基准时间限制：1 秒空间限制：131072 KB 分值: 5 难度：1级算法题
约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。

约翰不在乎字母大小写。（也就是说字母F和f）的完美度相同。给定一个字符串，输出它的最大可能的完美度。例如：dad，你可以将26分配给d，25分配给a，这样整个字符串完美度为77。
Input
输入一个字符串S(S的长度 <= 10000)，S中没有除字母外的其他字符。
Output
由你将1-26分配给不同的字母，使得字符串S的完美度最大，输出这个完美度。
Input示例
dad
Output示例
77

果然重做经典问题总是会有收获，又学到了新的转换方法。

开始自己手写了一个大小写转换表：

 1 #include<iostream>
 2 #include<map>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int a[1000010];
 8 
 9 int main(){
10     string s;
11     map<char,int> m;
12     cin>>s;
13     int len=s.size();
14     for(int i=0;i<len;i++){
15         if(s[i]=='A')
16         s[i]='a';
17         if(s[i]=='B')
18         s[i]='b';
19         if(s[i]=='C')
20         s[i]='c';
21         if(s[i]=='D')
22         s[i]='d';
23         if(s[i]=='E')
24         s[i]='e';
25         if(s[i]=='F')
26         s[i]='f';
27         if(a[i]=='G')
28         s[i]='g';
29         if(s[i]=='H')
30         s[i]='h';
31         if(s[i]=='I')
32         s[i]='i';
33         if(s[i]=='J')
34         s[i]='j';
35         if(s[i]=='K')
36         s[i]='k';
37         if(s[i]=='L')
38         s[i]='l';
39         if(s[i]=='M')
40         s[i]='m';
41         if(a[i]=='N')
42         s[i]='n';
43         if(s[i]=='O')
44         s[i]='o';
45         if(s[i]=='P')
46         s[i]='p';
47         if(s[i]=='Q')
48         s[i]='q';
49         if(s[i]=='R')
50         s[i]='r';
51         if(s[i]=='S')
52         s[i]='s';
53         if(s[i]=='T')
54         s[i]='t';
55         if(a[i]=='U')
56         s[i]='u';
57         if(s[i]=='V')
58         s[i]='v';
59         if(s[i]=='W')
60         s[i]='w';
61         if(s[i]=='X')
62         s[i]='x';
63         if(s[i]=='Y')
64         s[i]='y';
65         if(s[i]=='Z')
66         s[i]='z';
67         m[s[i]]++;
68     }
69     int ans=26,sum=0,t=0;
70     map<char,int>::reverse_iterator it;
71     for(it=m.rbegin() ;it!=m.rend() ;it++){
72         a[t++]=(*it).second;
73     }
74     sort(a,a+t);
75     for(int i=t-1;i>=0;i--){
76         sum+=a[i]*ans;
77         ans--;
78     }
79     cout<<sum<<endl;
80     return 0;
81 }

略显麻烦。

这是改进后的大小写转换：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int a[30];
 7 
 8 int main(){
 9     string s;
10     int k;
11     memset(a,0,sizeof(a));
12     cin>>s;
13     int len=s.size();
14     for(int i=0;i<len;i++){
15         if(s[i]>='a'&&s[i]<='z')
16         k=s[i]-'a';
17         else
18         k=s[i]-'A';
19         //cout<<k<<endl;
20         a[k]++;
21     }
22     sort(a,a+26);
23     int sum=0;
24     for(int i=0;i<=25;i++){
25         sum+=a[i]*(i+1);
26     }
27     cout<<sum<<endl;
28     return 0;
29 }

通过减'a'直接得到对应减一的数值并采用计入数组，比上一个方法简便了许多，即使时间是一样的。