解题思路

这是一道贪心算法题目，主要思路如下：

  1. 统计每个字母出现的次数：

    • 使用长度为26的数组记录每个大写字母的出现次数

  2. 对字母出现次数进行排序：

    • 从大到小排序，这样可以优先选择出现次数最多的字母

  3. 贪心选择：

    • 从出现次数最多的字母开始选择
    • 如果剩余可选数量m大于等于当前字母出现次数，全部选择
    • 否则只选择m个，然后结束

  4. 计算得分：

    • 每组相同字母的得分为：选择数量的平方
    • 累加所有选择的得分

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long n, m;
    while(cin >> n >> m) {
        string str;
        cin >> str;
        
        // 统计字母出现次数
        vector<long long> count(26, 0);
        for(int i = 0; i < n; i++) {
            count[str[i] - 'A']++;
        }
        
        // 排序
        sort(count.begin(), count.end());
        
        // 贪心选择
        long long ans = 0;
        int k = 25;  // 从最大的开始
        while(m > 0) {
            if(m >= count[k]) {
                // 可以全部选择
                ans += count[k] * count[k];
                m -= count[k];
                k--;
            } else {
                // 只能选择部分
                ans += m * m;
                break;
            }
        }
        
        cout << ans << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            long n = sc.nextLong();
            long m = sc.nextLong();
            String str = sc.next();
            
            // 统计字母出现次数
            long[] count = new long[26];
            for(int i = 0; i < n; i++) {
                count[str.charAt(i) - 'A']++;
            }
            
            // 排序
            Arrays.sort(count);
            
            // 贪心选择
            long ans = 0;
            int k = 25;  // 从最大的开始
            while(m > 0) {
                if(m >= count[k]) {
                    // 可以全部选择
                    ans += count[k] * count[k];
                    m -= count[k];
                    k--;
                } else {
                    // 只能选择部分
                    ans += m * m;
                    break;
                }
            }
            
            System.out.println(ans);
        }
    }
}

def calculate_score(n, m, cards):
    # 统计字母出现次数
    count = [0] * 26
    for c in cards:
        count[ord(c) - ord('A')] += 1
    
    # 排序
    count.sort()
    
    # 贪心选择
    ans = 0
    k = 25  # 从最大的开始
    while m > 0:
        if m >= count[k]:
            # 可以全部选择
            ans += count[k] * count[k]
            m -= count[k]
            k -= 1
        else:
            # 只能选择部分
            ans += m * m
            break
    
    return ans

def main():
    while True:
        try:
            n, m = map(int, input().split())
            cards = input()
            print(calculate_score(n, m, cards))
        except EOFError:
            break

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度： - 其中 为字符串长度， 为字母表大小
  • 空间复杂度： - 需要一个数组存储字母出现次数