题意 给出一个由小写字母组成的字符串，找到一个数组{a₁...a₂₆}={$1,\mathrm{2...26}1,2...26$},使得${\sum }_{i=1}^n{a}_i\ast p_i\backslash sum\_\{i=1\}^n\; a\_i*p\_i$最大，其中$p_{i}p\_i$是第i个字母出现的次数。

解答

容易发现由排序不等式，只需要让出现次数最多的字母对应26，次多的字母对应25....以此类推，即可以得到最大的答案^[1]。

代码如下。

#include<bits/stdc++.h>
using namespace std;
int p[30];//存储字母出现次数的数组
bool cmp(int a,int b){return a>b;}//将数组降序排列
int main()
{
    int Q;
    string k;
    cin >> Q;//输入数据组数
    while(Q--)
    {
        memset(p,0,sizeof p);//初始化
        int ans=0;
        cin >> k;
        int len=k.length();
        for(int i=0;i<len;i++) p[k[i]-'a']++;//统计字符出现次数
        sort(p,p+26,cmp);//排序
        for(int i=0;i<26;i++) ans+=(26-i)*p[i];//计算漂亮度
        cout << ans << endl;
    }
}

时间复杂度:$O(Qlen)O(Qlen)$，需要遍历每个字符串的每个字母。

空间复杂度:$O(len)O(len)$,存储字符串所需空间。

$[1][1]$:该贪心的证明如下，假设某组数据取得最大值时26不对应出现次数最多的字母，设该字母对应的值为$pp$，26对应的字母和出现最多的字母出现次数分别为$t_1,t_{2}t\_1,t\_2$，则交换两字母对应值，可得前后漂亮度差为$26(t_2-t_1)+p(t_1-t_2)=(26-p)(t_2-t_1)>026(t\_2-t\_1)+p(t\_1-t\_2)=(26-p)(t\_2-t\_1)>0$，矛盾，故取得最大值时26一定对应出现次数最多的字母，以此类推可证贪心成立。

证明成立的一个例子

(https://uploadfiles.nowcoder.com/images/20211215/236381190_1639546101126/21DE0D1794E83BB881EE23FFC1494E28)