传智杯 第六届-复赛-第二场-C

题目描述:

        小红有一个长度为 n 的字符串 s，仅包含小写字母，小红可以选出 k 个字符，组成一个新的字符串 t，对于 t 的每一个字符 ti，如果 ti在 t中出现的次数为 y，则小红会获得 y的分数，现在小红想知道，她最多能获得多少分。

输入描述:

        第一行两个整数 n,k，表示字符串 s 的长度和小红选出的字符个数。第二行一个字符串 sss，表示小红的字符串。（1≤k≤n≤10^5）

输出描述:

        输出一个整数，表示小红最多能获得的分数。

示例1

输入:

5 3
aabcc

输出:

5

说明:

        小红选出 "acc"，第一个字符获得 1 分，第二个字符获得 2 分，第三个字符获得 2 分，一共获得 5 分。

解题思路： 

        由题可知，我们想要得到最大的分数，那么我们就需要每次选择个数最多的字符。所以我们在输入的时候就记录下每个字符出现的次数，然后将这些次数按照从大到小的顺序进行排序，这样就可以依次得到出现次数最大的字符。

代码：

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

//排序
bool cmp(int a, int b)
{
	return a > b;
}

signed  main()
{
	//输入、记录每个字符的分数
	int n;   //字符个数
	int k;    //选出字符个数
	cin >> n >> k;
	char* arr1 = new char[n];    //字符
	int arr2[26] = {0};    //字符
	for (int i = 0;i < n;i++)
	{
		cin >> arr1[i];
		arr2[arr1[i] - 'a']++;    //对应字符的数量++
	}

	//排序
	sort(arr2, arr2 + 26,cmp);

	//依次选出字符
	int num = 0;   //加入的个数
	int count = 0;   //分数
	for (int i = 0;i < 26;i++)
	{
		if (num + arr2[i] <= k)   //可以全部加入
		{
			num += arr2[i];
			count = count + arr2[i] * arr2[i];
		}
		else   //部分加入
		{
			count = count + (k - num) * (k - num);
			num = k;
		}
		if (num == k)   //已加满
		{
			break;
		}
	}

	//输出
	cout << count << endl;

	system("pause");
}