题目分析

我们有 n 个行李物品，每个行李物品用一个小写字母表示。对于每种物品，最多可以携带 k 个相同的物品。我们需要计算小美最多可以携带多少个行李物品。

解题思路

1. 数据结构选择：题目给定的物品是由小写字母组成，我们可以统计每个字母出现的频率，然后决定最多可以携带多少个同类物品。这里可以使用一个 字典 或者 Counter 来统计每个字符的出现次数。

2. 计算思路：

   • 对于每种物品，我们可以携带的数量是该物品出现次数和 k 中较小的一个。例如，如果某个物品出现了 3 次，但 k=2，那么最多只能携带 2 个该物品。
   • 对所有物品的携带数量求和，得到最终的结果。

3. 步骤：

   • 统计每种物品的出现次数。
   • 对于每种物品，计算可以携带的数量（取该物品出现次数与 k 的较小值）。
   • 最终结果为所有物品的携带数量之和。

算法分析

• 时间复杂度：统计每个物品的频率是 O(n)，其中 n 是物品的总数。然后计算每个物品的携带数量是 O(1)，总共有 26 种字符，因此总时间复杂度为 O(n)。
• 空间复杂度：我们需要一个 字典 或者 Counter 来存储每种物品的出现次数，最坏情况下，空间复杂度是 O(26) = O(1)，因为最多只有 26 个字母。

代码实现

Python

from collections import Counter

def max_baggage(n, k, items):
    # 统计每种物品出现的频率
    counter = Counter(items)
    
    # 计算可以带的行李物品总数
    total_baggage = 0
    for count in counter.values():
        total_baggage += min(count, k)
    
    return total_baggage

# 输入
n, k = map(int, input().split())
items = input().strip()

# 输出
print(max_baggage(n, k, items))

JAVA

import java.util.*;

public class Main {
    public static int maxBaggage(int n, int k, String items) {
        // 使用 HashMap 统计每个物品出现的频率
        Map<Character, Integer> counter = new HashMap<>();
        for (char item : items.toCharArray()) {
            counter.put(item, counter.getOrDefault(item, 0) + 1);
        }
        
        // 计算最多可以带的物品总数
        int totalBaggage = 0;
        for (int count : counter.values()) {
            totalBaggage += Math.min(count, k);
        }
        
        return totalBaggage;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.nextLine();  // Consume the newline
        String items = scanner.nextLine();
        
        // 输出
        System.out.println(maxBaggage(n, k, items));
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

int maxBaggage(int n, int k, const string& items) {
    // 使用 unordered_map 统计每个物品出现的频率
    unordered_map<char, int> counter;
    for (char item : items) {
        counter[item]++;
    }
    
    // 计算最多可以带的物品总数
    int totalBaggage = 0;
    for (auto& entry : counter) {
        totalBaggage += min(entry.second, k);
    }
    
    return totalBaggage;
}

int main() {
    int n, k;
    cin >> n >> k;
    string items;
    cin >> items;
    
    // 输出
    cout << maxBaggage(n, k, items) << endl;
    return 0;
}

题目内容

小美准备出游，她有 $n$ 个行李物品，每个行李物品用小写字母表示。

现在规定每种行李物品携带不能超过 $k$ 个，求小美最多可以带多少个行李物品。

输入描述

第一行两个整数 $n,k(1≤n≤10^5,1≤k≤n)$ 表示行李物品个数和每种物品限带的个数。

第二行一个长度为 $n$ 的字符串，表示 $n$ 个行李物品，输入保证仅由小写字母组成。

输出描述

一个整数，表示最多可以带的行李物品总数。

样例1

输入

3 1
aab

输出

2