【PTA】7-9 得到字符串的最小价值

Love The Way You Lie 2023-09-27 10:59 78阅读 0赞

有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值  
例如: 字符串"abacaba",里面包括4个'a',2个'b',1个'c',于是这个字符串的价值为4 \* 4 + 2 \* 2 + 1 \* 1 = 21  
有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。

#### 输入格式: ####

输入包括两行,第一行一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),其中只包含小写字母('a'-'z')。  
第二行包含一个整数k(0 ≤ k ≤ length),即允许移除的字符个数。

#### 输出格式: ####

输出一个整数,表示得到的最小价值。

#### 输入样例: ####

在这里给出一组输入。例如：

apple
    2

#### 输出样例: ####

在这里给出相应的输出。例如：

这里的思路是，定义一个数组用于统计26字母出现的次数，arr\[0\]用于记录a出现的次数，一次类推定义一个长度为26 的数组记录每个字母出现的次数，此时利用Arrays下的sort函数进行排序，排序后 因为还不能直接计算需要删除，删除后计算，要想最小价值，就得删出现最多，也就是数组里最大值以及bu排序后最后一个元素就是最大值，利用arr.length-1去处理他，处理后再次排序然后重复直到删除够

import java.util.*;
    import java.lang.*;
    
    public class Main{
        public static void main(String[] args){
            Scanner scanner = new Scanner(System.in);
            String s = scanner.nextLine();
            int n = scanner.nextInt();
            
            int[] arr = new int[26];
            for(int i = 0;i < s.length();i++){
                arr[s.charAt(i)-97]+=1;
            }
            
            int length = arr.length;
            Arrays.sort(arr);
            while(n-- != 0){
                arr[arr.length - 1] -= 1;
                Arrays.sort(arr);
            }
            
            int result = 0;
            for(int i = 0;i < length;i++){
                if(arr[i] != 0){
                  result+=Math.pow(arr[i],arr[i]);
                }
            }
            System.out.println(result);
        }
    }