给你n张卡片,卡片上仅包含大写英文字母,现你可从这n张卡片中选出k张,要求得到尽可能高的分数。
关于分数的计算方式,在你所选择的k张卡片中,含有相同字母的卡片分数为卡片数乘以相同卡片个数。
就样例而言,选择九张D和其他任意一张,得到的结果为9*9+1 。
输入包含两行,第一行含两个整数n,k(0<k<=n<=1,000,000)
第二行为每张卡片上的字母
输出仅包含一行,输出尽可能高的分数
15 10 DZFDFZDFDDDDDDF
82
import java.util.Scanner; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { while (sc.hasNext()) { //获取输入数据 String[] str0 = sc.nextLine().split(" "); int n = Integer.parseInt(str0[0]); int k = Integer.parseInt(str0[1]); String str = sc.nextLine(); //处理输入数据->键值对 int len = str.length(); HashMap<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = 0; i < len ; i++) { char ch=str.charAt(i); if(map.containsKey(ch)) { map.put(ch, map.get(ch)+1); }else { map.put(ch, 1); } } //对值排序 ArrayList<Integer> list = new ArrayList<Integer>(map.values()); long grade = 0; // Collections.sort(list); // Collections.reverse(list); Collections.sort(list,new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { // TODO Auto-generated method stub return o2-o1; } }); //计算结果 for (int i : list) { if (i >= k) { grade += (long) k * k; System.out.println(grade); break; } else { grade += (long) i * i; k -= i; } } } } }
import java.util.*; public class Main { public void calcu(long k, int n, String s){ //使用HashMap Map<Character,Integer> map = new TreeMap<Character,Integer>(); int len=0; for(int i=0;i<s.length();i++) { // 如果包含该键值对,值+1 if(map.containsKey(s.charAt(i))){ int num=map.get(s.charAt(i))+1; map.remove(s.charAt(i)); map.put(s.charAt(i), num); }else{ //如果不包含,创建新键值对 map.put(s.charAt(i), 1); len++; } } int []b = new int [len]; int t=0; //用来下标滑动 int ex=0; long max=0; //遍历HashMap,将值存进数组 for(Character key : map.keySet()){ int num =map.get(key); b[t]=num; ++; } //对数组排序,冒泡 for(int i=0;i<len;i++){ for(int j=0;j<len-i-1;j++){ if(b[j]>b[j+1]){ ex=b[j]; b[j]=b[j+1]; b[j+1]=ex; } } } //选值 for(int i=len-1;i>=0;i--){ if(b[i]>=k){ max = max+k*k; System.out.println(max); break; }else{ max = max+b[i]*b[i]; k = k-b[i]; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); Main m = new Main(); while(sc.hasNext()) { int n = sc.nextInt(); long k = sc.nextLong(); String s= sc.next(); m.calcu(k, n, s); } } }