1 second
256 megabytes
standard input
standard output
Appleman has n cards.
Each card has an uppercase letter written on it. Toastman must choose k cards from Appleman's cards.
Then Appleman should give Toastman some coins depending on the chosen cards. Formally, for each Toastman's card i you
should calculate how much Toastman's cards have the letter equal to letter on ith, then sum up all these quantities,
such a number of coins Appleman should give to Toastman.
Given the description of Appleman's cards. What is the maximum number of coins Toastman can get?
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105).
The next line contains n uppercase letters without spaces — the i-th
letter describes the i-th card of the Appleman.
Print a single integer – the answer to the problem.
15 10 DZFDFZDFDDDDDDF
82
6 4 YJSNPI
4
In the first test example Toastman can choose nine cards with letter D and
one additional card with any letter. For each card with D he will get 9 coins and for the additional card he will get 1 coin.
题意：给出一个数量为n的牌组序列，你从中取k张，问你取得最大值是多少，分数的判定规则为，自己所得的每种相同字母的个数即为该种字母每个所得的分数，比如；得到的字母是DDDDDDDDDF那么所得的分时是9*9+1*1=82
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<cstdlib>
#define LL long long
const int Max=100100;
char str[Max];
char letter[27]={'0','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
LL num[27];
using namespace std;
typedef struct Node
{
LL xm;
LL xp;
}node;
node s[27];
bool cmp(Node u,Node v)
{
return u.xm>v.xm;
}
int main()
{
LL n,m,k,i,j;
LL maxn,res,p;
LL sum;
while(cin>>n>>k)
{
map<int,int>Map;
memset(num,0,sizeof(num));
for(i=1;i<=n;i++)
{
cin>>str[i];
res=str[i]-'A'+1;
num[res]++;
Map[res]=1;
}
//for(i=1;i<=26;i++)
//cout<<num[i]<<endl;
sum=0;
maxn=0;
res=0;
for(i=1;i<=26;i++)
{
s[i].xm=num[i];
s[i].xp=i;
}
sort(s+1,s+27,cmp);
for(i=1;i<=26;i++)
{
if(k>=s[i].xm&&k>0)
{
sum+=s[i].xm*s[i].xm;
k-=s[i].xm;
Map[res]=0;
}
else
{
sum+=k*k;
k=0;
}
if(k==0)
break;
}
cout<<sum<<endl;
}
return 0;
}
/*
15 10
DZFDFZDFDDDDDDF
6 4
YJSNPI
*/