LuxakyLuee是一个非常爱玩的人。 有一天一个叫Kevin·Feng的人向LuxakyLuee发来游戏邀请。 Kevin·Feng摆了一地的键盘冒,上面都是英文字母,让LuxakyLuee从其中任选k个。 选完之后进入清算时间,每一个键帽的分数是总共选取的的该种键帽字母的数量。 如果LuxakyLuee足够机智他能得多少分呢。
多组测试数据。 每组数据有两行。 第一行为n和k,n为键盘冒的数量,k为选取的键盘冒的个数。(1 ≤ k ≤ n ≤ 100000). 第二行为地上的键盘冒(均为大写字母)。
每组数据输出一行,为LuxakyLuee的最高可能得分。
温馨提示:输入时用%s输入字符串,输出时用%lld, OJ 不支持 %I64d !!!
【解析】
这道题我们就让字母数量越多的那个字母先拿我们可以先统计字母的数量,之后我们再进行排序,然后再进行筛选就好了
#include<iostream> #include<string.h> #include<string> #include<cstdio> #include<algorithm> #define MAXN 100010 using namespace std; int main() { long long n,k,i,sum; char s[MAXN]; while(~scanf("%lld%lld",&n,&k)) { getchar(); scanf("%s",s); long long a[26]={0}; for(i=0;i<n;i++) { a[s[i]-65]=a[s[i]-65]+1; } sort(a,a+26); n=25; sum=0; while(k!=0) { if(k>=a[n]) { k=k-a[n]; sum=sum+a[n]*a[n]; } else if(k<a[n]) { sum+=k*k; k=0; } n--; } printf("%lld\n",sum); } return 0; }