首页 > 试题广场 > 字母卡片
[编程题]字母卡片
  • 热度指数:5115 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给你n张卡片,卡片上仅包含大写英文字母,现你可从这n张卡片中选出k张,要求得到尽可能高的分数。
关于分数的计算方式,在你所选择的k张卡片中,含有相同字母的卡片分数为卡片数乘以相同卡片个数。
就样例而言,选择九张D和其他任意一张,得到的结果为9*9+1 。

输入描述:
输入包含两行,第一行含两个整数n,k(0<k<=n<=1,000,000)

第二行为每张卡片上的字母


输出描述:
输出仅包含一行,输出尽可能高的分数
示例1

输入

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;
}

发表于 2019-07-12 19:20:55 回复(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 ; 
}

发表于 2020-02-11 16:50:59 回复(2)
from collections import Counter
while 1:
    try:
        a = int(input().split()[1])
        b,p = Counter(input()),0
        for i in sorted([(b[i],i) for i in b])[::-1]:
            if i[0] < a:
                a,p = a - i[0],p + i[0] ** 2
            else:
                print(p + a ** 2)
                break
    except:
        break

发表于 2020-03-17 22:22:09 回复(0)
直接对n张卡片的每个字母进行计数,按计数进行降序排列,然后顺序去凑k张卡片就可以了。
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


发表于 2021-01-31 11:02:47 回复(0)
JAVA思路:
首先遍历字符串,用HashMap存值,key是字符,value是次数。
因为本题不关注最后是什么字母,只需把values值摘出来,从大到小排序。
遍历排序后的数组或集合,直到达到k,返回一个long的结果
需要注意的点是结果是long时要对int强转
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;
				}
			}

		}
	}

}


编辑于 2020-07-28 15:58:24 回复(0)
# 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




发表于 2019-09-04 14:21:43 回复(0)
#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;
}

发表于 2019-09-02 09:55:55 回复(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);
    }
    }
}


编辑于 2019-08-16 15:14:46 回复(3)
#include<iostream>
#include<string>
#include<algorithm>
int main()
{
    long long n,k;
    std::string s;
    while(std::cin>>n>>k)
    {
        std::cin>>s;
        long long a[26]={0};
        for(long long i=0;i<n;i++)a[s[i]-'A']++;
        std::sort(a,a+26);
        long long count=0;
        for(int j=25;j>=0;j--)
        {
            if(a[j]>=k)
            {
                count+=k*k;
                std::cout<<count<<std::endl;
                break;
            }
            else
            {
                count+=a[j]*a[j];
                k-=a[j];
            }
        }
    }
    return 0;
}
发表于 2020-09-10 23:42:06 回复(0)
这题目的描述水平小学二年级不能更高了吧
发表于 2020-08-27 17:49:02 回复(0)
#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语言的,可惜超时了
发表于 2020-08-12 01:31:31 回复(0)
///
/// 存入字典,然后对key值排序,然后输出结果。例子里面用long long着实是来恶心人的
///
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
    int cnt,tar;
    while(cin>>cnt>>tar)
    {
        map<char,int> dict;
        char c;
        for(int i=0;i<cnt;i++)
        {
            cin>>c;
            if(dict.find(c)!=dict.end())
            {
                dict[c] += 1;
            }
            else
            {
                dict[c] = 1;
            }
        }
        vector<pair<char,long long>> sorted;
        for(auto iter=dict.begin();iter!=dict.end();iter++)
        {
            sorted.push_back(make_pair(iter->first,iter->second));
        }
        sort(sorted.begin(),sorted.end(),[](const auto &l,const auto &r)
             {
                 return l.second>r.second;
             }) ;
            long long counted = 0;
        long long sum = 0;
        for(long long k=0;k<sorted.size();k++)
        {
            //cout<<sorted[k].first<<sorted[k].second<<endl;
            if(counted+sorted[k].second>tar)
            {
                // more than can hold
                sum += (tar-counted)*(tar-counted);
                break;
            }
            sum += sorted[k].second*sorted[k].second;
            counted+=sorted[k].second;
        }

        cout<<sum<<endl;
    }
    return 0;
}
发表于 2020-08-08 14:08:22 回复(0)
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)

发表于 2020-08-05 23:25:29 回复(0)
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);   
        }
    }
}

发表于 2020-07-31 20:03:42 回复(0)
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)

题目没有说一次给出多个样例啊,感觉这个还是得讲出来吧。
发表于 2020-06-08 20:42:37 回复(0)
#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;
}
发表于 2020-06-06 16:27:48 回复(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);
    }
}

发表于 2020-05-06 16:47:00 回复(0)

题目描述得很奇怪,“含有相同字母的卡片分数为卡片数乘以相同卡片个数”,不知道这个“卡片数”是指总卡片数还是当前字母的卡片数,有歧义,根据大家对题目的理解写了答案:

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);
        }
    }
}
编辑于 2020-04-16 13:14:35 回复(0)
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);
    }
}

发表于 2020-04-05 03:01:43 回复(0)
我的代码有问题,有一个样例没有通过,求问我的哪里出错了?我自己检查一直没找出来。
#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;
}


发表于 2019-09-21 13:25:31 回复(0)