字符串价值

思路：

先计算每个字母出现次数，然后每次减出现次数最高的那个，注意：没减一次最大值会变化。

import java.util.Arrays;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputString = scanner.nextLine();
        int k = scanner.nextInt();
        scanner.close();
        // 记录每个元素出现次数
        int[] numArray = new int[26];
        for (int i = 0; i < inputString.length(); i++) {
            numArray[inputString.charAt(i) - 'a']++;
        }
        // 按照出现次数进行排序
        Arrays.sort(numArray);

        for (int i = numArray.length - 1; i >= 1; i--) {
            // 该值必须大于后面的值，加上下面的排序保证每次都是减出现次数最多的那个位置值
            while (numArray[i] > 0 && numArray[i] >= numArray[i - 1] && k > 0) {
                numArray[i]--;
                k--;
                // 每次减完排序，一直减最大的那个
                Arrays.sort(numArray);
            }
        }

        long sum = 0;
        for (int i = 0; i < numArray.length; i++) {
            sum += numArray[i] * numArray[i];
        }

        System.out.println(sum);
    }
}

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<utility>
#include<cmath>

using namespace std;

class Solution {
public:
	/**********************************字符串价值********************************************/
	void returnMinValue() {
		string str;
		cin >> str;
		map<string, int> dir;
		while (!str.empty()) {
			++dir[str.substr(0, 1)];
			str.erase(0, 1);
		}
		priority_queue<pair<int, string>> pque;
		for (auto begin = dir.begin(); begin != dir.end();++begin) 
			pque.push(make_pair((*begin).second, (*begin).first));
		int k = 0;
		cin >> k;
		int res = 0;
		while (!pque.empty()) {
			pair<int, string> curr = pque.top();
			pque.pop();
			int dif = curr.first - pque.top().first;
			if (dif >= k) {
				res += pow((curr.first - k), 2);
				while (!pque.empty()) {
					res += pow((pque.top().first), 2);
					pque.pop();
				}
				cout << res << endl;
				return;
			}
			else {
				curr.first -= (dif + 1);
				k -= (dif + 1);
				pque.push(curr);
			}
		}
		
	}
};

int main() {
    
	Solution s3;
	s3.returnMinValue();
	system("pause");
	return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main()
{
    std::string input("");
    std::cin >> input;
    int k = 0;
    std::cin >> k;
    int arr[26] = {0};
    for (int i = 0; i < input.length(); i++)
    {
        arr[input.at(i) - 'a'] += 1;
    }
    std::vector<int> sort_arr;
    for (int i = 0; i < 26; i++)
    {
        if (arr[i] > 0)
            sort_arr.push_back(arr[i]);
    }
    int t = 0;
    std::sort(sort_arr.begin(), sort_arr.end());
    int max_site = sort_arr.size() - 1;
    int second_site = max_site;
    while(k > 0)
    {
        /*
            最小的价值不是让最大的数减k,而是让各个数尽量小
            首先要让最大的数减到和第二大的数一样，然后再将第一和第二大的数减到和第三大的数一样
            如果所有数都一样，再依次减一
            直到K用尽
            */
        if (sort_arr[max_site] == sort_arr[second_site])
        {
            if (second_site >= 0)
            {
                int t = second_site;
                for (int i = second_site; i >= 0; i--)
                {
                    if (sort_arr[i] < sort_arr[second_site])
                    {
                        t = i;
                        break;
                    }
                }
                second_site = t < second_site ? t : -1;
            }
            
        }
        for (int i = sort_arr.size() - 1; i > second_site && k > 0; i--)
        {
            sort_arr[i] -= 1;
            k -= 1;
        }
    }
    
    int64_t value = 0;
    for (int i = 0; i < sort_arr.size(); i++)
    {
        value += (sort_arr[i] * sort_arr[i]);
    }
    std::cout << value << std::endl;
    return 0;
}

s = str(input())
k = int(input())
d = {}
for c in set(s):
    d[c] = s.count(c)
nums = list(d.values())
minus = 0
while minus < k:
    nums.sort(reverse=True)
    nums[0]-=1
    minus+=1
print(sum([n**2 for n in nums]))

import java.util.*;
public class Main{
  public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int k = sc.nextInt();
        sc.close();
        int[] nums = new int[26];
        int res = str.length() - k;
        if (res < 2) {
            System.out.println(res);
            return;
        }

        for (int i = 0; i < str.length(); ++i) {
            nums[str.charAt(i) - 'a']++;
        }
      
        Arrays.sort(nums);
        int maxIndex = 25,i = 25;
        res = 0;
        while (k > 0) {
            if (maxIndex == 0) {
                nums[maxIndex] -= k;
                k = 0;
            }
            while (k> 0 && nums[maxIndex] > nums[maxIndex - 1])
            {
                for( i = maxIndex;k>0 &&i<26;++i){
                    --nums[i];
                    --k;
                }
            }
            --maxIndex;
        }
        for (int j = 0;j<=maxIndex;++j){
            res += (int)Math.pow(nums[j], 2);
        }
        if(maxIndex<25) {
            res += (i - maxIndex  - 1) * (int) Math.pow(nums[maxIndex + 1], 2);
            if(i<26)
                res += (26 - i) * (int) Math.pow(nums[i], 2);
        }
        System.out.println(res);
    }
}

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        int num = Integer.parseInt(bf.readLine());
        int[] array = Delete(str,num);
        int count=0;
        for (int a:array){
            count+=a*a;
        }
        System.out.println(count);
    }
    static int[] Delete(String str,int num){
        int[] array = new int[26];
        for(int i=0;i<str.length();i++){
            array[(int)str.charAt(i)-'a']++;
        }
        for (int i=0;i<num;i++){
            Arrays.sort(array);
            array[array.length-1]--;
        }
        return array;
    }
}

input_str=input()
remove_n=int(input())
input_list=[i for i in input_str.strip()]
k={}
for i in input_list:
    if i in k:
        k[i]+=1
    else:
        k[i]=1
list_n=[k[i] for i in k]
while remove_n:
    max_index=list_n.index(max(list_n))
    list_n[max_index]-=1
    remove_n-=1
s=0
for i in list_n:
    s+=i*i
print(s)

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int k = sc.nextInt();
        int[] array = new int[26];
        //array[0]代表a出现的次数，后面依次类推
        for(int i = 0; i < str.length(); i ++){
            char temp = str.charAt(i);
            int num = temp - 'a';
            array[num]++;
        }
        //每次array数组中最大的数减一，为了找到最大的数，通过Arrays.sort()进行排序
        int count = 0;
        while(k != count){
            Arrays.sort(array);
            if(array[array.length-1] != 0){
                array[array.length-1]--;
                count ++;
            }
        }
        
        int sum = 0;
        //数组的平方和就是最后的结果
        for(int j = 0; j < array.length; j ++){
            sum += Math.pow(array[j], 2);
        }
        System.out.println(sum);
        return;
    }
}