题意:
每个字母都有一个“漂亮度”,范围在1到26之间。
没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。
给出一个字符串,计算最大可能的“漂亮度”。
方法一:
贪心
思路:对字符串的每种字母计数,字母忽略大小写。然后根据贪心,排序。(让数值最大的字母*26+数值次大的字母*25+......)以此类推。
#include <bits/stdc++.h> using namespace std; int cnt[26];//计数数组 int main(){ int n; string s; cin >> n; while(n--){ memset(cnt,0,sizeof(cnt)); cin >> s; int len=s.size(); for(int i=0;i<len;i++){ if(s[i]>='a') s[i]-=32; cnt[s[i]-'A']++;//对字母计数 } sort(cnt,cnt+26);//排序 int sum=0; int num=26; for(int i=25;i>=0;i--){//贪心 if(cnt[i]==0) break; sum+=cnt[i]*(num--);//求和 } cout << sum << endl; } return 0; }
时间复杂度:空间复杂度:
方法二:
优先队列
思路:思路同方法一相同,但利用优先队列来排序,每次弹出最大值。
#include <bits/stdc++.h> using namespace std; int cnt[26];//计数数组 int main(){ int n; string s; cin >> n; while(n--){ memset(cnt,0,sizeof(cnt)); cin >> s; int len=s.size(); for(int i=0;i<len;i++){ if(s[i]>='a') s[i]-=32; cnt[s[i]-'A']++;//对字母计数 } priority_queue<int> q;//优先队列 for(int i=0;i<26;i++) q.push(cnt[i]); int sum=0; int num=26; while(!q.empty()){//贪心 sum+=q.top()*(num--);//求和 q.pop(); } cout << sum << endl; } return 0; }
时间复杂度:空间复杂度: