首页 > 代码库 > Codeforces Round #263 (Div. 2) proB
Codeforces Round #263 (Div. 2) proB
题目:
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.
题意分析:
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char s[110000]; int j[500],cn[500]; void solve() { int n,k; long long ans=0; scanf("%d%d",&n,&k); scanf("%s",s); int len=strlen(s); for(int i=0; i<len; i++) { j[s[i]]++; } while(k) { k--; int w=0,Max=0; for(int i='A'; i<='Z'; i++) { if(j[i]>Max&&cn[i]<j[i]) { Max=j[i]; w=i; } } cn[w]++; } for(int i='A'; i<='Z'; i++) { ans+=1LL*cn[i]*cn[i]; } cout<<ans<<endl; } int main() { solve(); return 0; }
Codeforces Round #263 (Div. 2) proB