给你n张卡片,卡片上仅包含大写英文字母,现你可从这n张卡片中选出k张,要求得到尽可能高的分数。
关于分数的计算方式,在你所选择的k张卡片中,含有相同字母的卡片分数为卡片数乘以相同卡片个数。
就样例而言,选择九张D和其他任意一张,得到的结果为9*9+1 。
输入包含两行,第一行含两个整数n,k(0<k<=n<=1,000,000)
第二行为每张卡片上的字母
输出仅包含一行,输出尽可能高的分数
15 10 DZFDFZDFDDDDDDF
82
#include <bits/stdc++.h> using namespace std; int main() { long long n,m; while(cin>>n>>m) { string str; cin>>str; vector<long long> v(26,0); for(int i = 0;i<n;i++) v[str[i]-'A']++; sort(v.begin(), v.end()); long long k = 25,ans = 0; while(m>0) { if(m>=v[k]) { ans+=v[k]*v[k]; m=m-v[k]; k--; } else { ans+=m*m; break; } } cout<<ans<<endl; } return 0; }
/*谜之题意+多组输入从来不提醒一下的- - 。*/ #include <bits/stdc++.h> #define LL long long using namespace std ; int main(){ LL a[30] ; string s ; int n , k ; while( cin >> n >> k ){ cin >> s ; memset( a , 0 , sizeof(a) ) ; for( int i = 0 ; i < n ; i++ ){ a[(int)s[i]-'A'] ++ ; } sort( a , a + 26 ) ; LL res = 0 ; for( int i = 25 ; i >= 0 ; i-- ){ LL v = min( (LL)k , a[i] ) ; res += v * v ; k -= v ; } cout << res << endl ; } return 0 ; }
from collections import defaultdict while 1: try: n, k = map(int, input().strip().split()) cards = list(input().strip()) counter = defaultdict(lambda: 0) # 对每个字母进行计数 for card in cards: counter[card] += 1 # 每个字母按计数降序排列 counter_new = sorted(counter.items(), key=lambda x: -x[1]) score = 0 for alpha, count in counter_new: if count < k: # 此时字母有count张,还未凑满k张,分数直接+count**2 score += count**2 k -= count else: # 此时字母无法利用全部的count张牌加分,分数只能+k**2 print(score + k**2) break except: break
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; } } } } }
# coding: utf-8 while True: try: n, k = list(map(int, input().strip().split(' '))) cards = input() c_c = {} for card in cards: if card in c_c.keys(): c_c[card] += 1 else: c_c[card] = 1 values = list(c_c.values()) values.sort() values.reverse() result = 0 for value in values: if k >= value: result += value**2 k -= value else: result += k**2 break print(result) except: break
#include <bits/stdc++.h> #define ll long long using namespace std; bool cmp(int a, int b){ return a>b; } int main(){ ll n,k,sum=0; string s; while(cin>>n>>k){ ll sum = 0; cin>>s; ll a[26]; memset(a,0,sizeof(a)); for(int i=0;i<n;i++){ a[s[i]-'A']++; } sort(a,a+26,cmp); int t=0; while(k){ if(k>=a[t]){ sum += a[t]*a[t]; k -= a[t]; }else{ sum += k*k; k = 0; } t++; } cout<<sum<<endl; } return 0; }
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); } } }
#include <stdio.h> int n; int main(){ while(scanf("%d",&n)!=EOF) { char a[n]; int b[n]; int i,k,tmp=0; scanf("%d",&k); scanf("%s",a); for(int i=0;i<n;i++){ a[i]=(a[i]-'A'); }//转为数字 int x,y,z=0; for(int z=(n-1);z>0;z--){ for(x=0;x<z;x++){ y=(x+1); if(a[x]>a[y]){ tmp=a[x]; a[x]=a[y]; a[y]=tmp; } } }//排序 int count=1; for(z=0;z<n-1;z++){ x=z; y=(z+1); b[z]=0; if(a[x]==a[y]){ count++; b[z]=0; } else { b[z]=count; count=1; } if(z==(n-2)){ b[z]=count; b[n-1]=0; } }//数相同的个数,保存到数组b for(int z=(n-1);z>0;z--){ for(x=0;x<z;x++){ y=(x+1); if(b[x]>b[y]){ tmp=b[x]; b[x]=b[y]; b[y]=tmp; } } }//数组b排序 int res=0; for(z=(n-1);k>0;z--){ if(k>b[z]){ res=(res+(b[z]*b[z])); k=(k-b[z]); } else { res=(res+(k*k)); k=0; } }//取牌,计算 printf("%d\n",res); } }C语言的,可惜超时了
from collections import Counter import sys lines = [line for line in sys.stdin] for i in range(0, len(lines), 2): n, k = map(int, list(lines[i].split())) cards = lines[i + 1] cnt = Counter(cards) cnt = sorted(cnt.values()) res = 0 while k > 0: cur = min(cnt.pop(), k) k -= cur res += cur*cur print(res)
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n, k; while (in.hasNextInt()) { n = in.nextInt(); k = in.nextInt(); in.nextLine(); String s = in.nextLine(); Map<Character, Integer> map = new HashMap<>(); for (char c : s.toCharArray()) { int count = map.getOrDefault(c, 0); map.put(c, count + 1); } Queue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); for (char c : map.keySet()) { pq.offer(map.get(c)); } long ans = 0; while (!pq.isEmpty()) { if (k == 0) break; int num = Math.min(k, pq.poll()); k -= num; ans += (long)num * num; } System.out.println(ans); } } }
import sys if __name__=="__main__": lines = sys.stdin.readlines() while lines: [n, k] = list(map(int, lines.pop(0).strip().split())) nums = lines.pop(0).strip() from collections import Counter a = dict(Counter(nums)) A = sorted(dict(Counter(nums)).values()) if k <= A[-1]: print(k*k) else: A = A[::-1] res = 0 while k > A[0]: res += A[0]*A[0] k -= A[0] A.pop(0) res += k*k print(res)
#include<bits/stdc++.h> using namespace std; int main(){ int n,k; while(cin>>n>>k) { string s; cin>>s; map<char,int>mp; for(char c:s) mp[c]+=1; vector<long long>v; for(auto t:mp) v.push_back(t.second); sort(v.rbegin(),v.rend()); // 注意数据类型 有坑 int要溢出的 long long score = 0; for(int i=0;i<v.size();++i){ if(k==0) break; if(k>=v[i]) { score+=v[i]*v[i]; k-=v[i]; } else { score+=k*k; k = 0; } } cout<<score<<endl; } return 0; }
/* 可以通过测试用例,提交的时候请检查是否存在数组越界等非法访问情况, 求大佬帮忙看看 */ import java.util.Scanner; import java.util.HashMap; import java.util.Arrays; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); long n=in.nextLong(); long k=in.nextLong(); String a=in.next(); char []b=a.toCharArray(); HashMap<Character,Integer> map=new HashMap<>(); HashMap<Integer,Character> mapkey=new HashMap<>(); for(int i=0;i<b.length;i++){ if(map.containsKey(b[i])!=true) {map.put(b[i],0); mapkey.put(i,b[i]);} } long [] c =new long [map.size()]; for(int i=0;i<map.size();i++){ long count =0; for(int j=0;j<b.length;j++){ if(mapkey.get(i).equals(b[j])){ count++; } } c[i]=count; } Arrays.sort(c); long num=0; for(int i=c.length-1;i>=0;i--){ if(k>=c[i]) {num=c[i]*c[i]; k=k-c[i];} else{ num=num+k*k;break; } } System.out.println(num); } }
题目描述得很奇怪,“含有相同字母的卡片分数为卡片数乘以相同卡片个数”,不知道这个“卡片数”是指总卡片数还是当前字母的卡片数,有歧义,根据大家对题目的理解写了答案:
import java.util.*; public class Main { private static void deal(int n, int k, String str) { int[] arr = new int[26]; for (int i = 0; i < n; i++) { int idx = str.charAt(i) - 'A'; arr[idx]++; } Arrays.sort(arr); int idx = 25; long res = 0L;; while (k >= 1 && idx >= 0) { if (k >= arr[idx]) { res += (long)arr[idx] * (long)arr[idx]; k -= arr[idx]; } else { res += (long)k * (long)k; k = 0; } idx--; } System.out.println(res); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int k = sc.nextInt(); String str = sc.next(); deal(n, k, str); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Card[] cards; while (sc.hasNext()) { int n = sc.nextInt();//卡片总数 int k = sc.nextInt();//选出的卡片数 char[] cardsArray = new char[n]; String s = sc.next(); for (int a = 0; a < n; a++) { cardsArray[a] = s.charAt(a); } long score = 0; Map<Character, Long> map = new HashMap<>(); for (char c : cardsArray) { map.put(c, map.getOrDefault(c, 0L) + 1); } cards = new Card[map.size()]; int j = 0; for (char c : map.keySet()) { cards[j++] = new Card(c, map.get(c)); } Arrays.sort(cards, new CardComparator()); for (int i = 0; i < map.size(); i++) { long num = cards[i].times; if (num <= k) { score += num * num; k -= num; } } System.out.println(score + k*k); } } } class Card { public char letter; public long times; public Card(char letter, long times) { this.letter = letter; this.times = times; } } class CardComparator implements Comparator<Card> { @Override public int compare(Card o1, Card o2) { return Long.compare(o2.times, o1.times); } }
#include<bits/stdc++.h> using namespace std; bool cmp(int a, int b){ return a > b; } int main(){ int n, k; while(cin >> n >> k){ long long cnt[26] = {0}; //char ch; string s; cin >> s; //cout << n << ' ' << s.size() << endl; n = n > s.size()? s.size(): n; k = k > n? n: k; for(int i = 0; i < n; i++){ //cin >> ch; cnt[s[i] - 'A']++; } sort(cnt, cnt + 26, cmp); long long curk = 0; long long sum = 0; long long last = k - curk; while(last > 0){ for(int i = 0; i < 26; i++){ last = k - curk; int num = cnt[i] > last? last: cnt[i]; sum = sum + num * num; curk = curk + num; }} cout << sum << endl;} return 0; }