排序不等式 && 贪心
前置知识:排序不等式:
$ a_1\leq a_2\leq a_3\leq…\leq a_n $
$ b_1\leq b_2\leq b_3 \leq…\leq b_n $
$ a_1b_1+a_2b_2+…+a_nb_n \geq a_1b_\alpha+a_2b_\beta+…+a_nb_\gamma\geq a_1b_n+a_2b_(n-1)+…+a_nb_1$
即最大值与最小值相乘,其最后累加结果最小
思路:
任意给出一个字符串,我们只需将其代数化
,赋予对应的权重
(除首字母外)权重最大的赋予数字0,权重最小的赋予9,
关键点:
我们要找到哪个字母对应数字0,即除首字母外权重最大的字符
int t=-1;//初始化指针
for(int i=0;i<10;i++)//找到权重最大的非首位字母
{
if(!st[i]&&(t==-1||w[i]>w[t])) t=i;
}
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10;
bool st[N];
int w[N];
char str[N];
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>str;
for(int i=strlen(str)-1,j=1;i>=0;i--,j*=10)
w[str[i]-'a']+=j;//字符数组中的每个数字出现一次,记录一次权值
//数组中的下标都对应一个固定的字母
st[str[0]-'a']=true;//首位标记
}
int t=-1;//初始化指针
for(int i=0;i<10;i++)//找到权重最大的非首位字母
{
if(!st[i]&&(t==-1||w[i]>w[t])) t=i;
}
for(int i=0,j=0;i<10;i++)//剔除0对应的元素
if(i!=t) w[j++]=w[i];
sort(w,w+9);
int res=0;
for(int i=0,j=9;i<9;i++,j--)
res+=w[i]*j;
cout<<res;
return 0;
}