「CSP-J 2024真题详解」洛谷P11227扑克牌问题：基于桶排序思想的高效解法 附完整C++代码

一、题目解读

本题要求计算标准扑克牌堆中缺失的牌数：

1. 输入规范：接收n张牌（1≤n≤52），每张牌以"数字+字母"格式表示

2. 核心算法：需要检测并统计缺失的扑克牌种类

3. 特殊规则：当n=1时固定返回51（最优解特殊情况处理）

4. 输出要求：直接输出缺失牌的数量

二、解题思路分析

1. 去重策略：

• 使用辅助数组s1存储不重复的牌

• 双重循环遍历实现O(n²)去重

2. 数学计算：

• 总牌数52减去实际出现的独特牌数

• 特殊情况n=1时直接返回51

3. 优化亮点：

• 避免使用STL容器，适合竞赛环境

• 显式处理边界情况提升效率

三、解题步骤分解

1. 输入阶段：

• 读取牌数n

• 存储所有牌到数组s

2. 去重处理：

   // bocket函数核心逻辑：
   for 每张输入牌:
       if 该牌未出现在s1数组:
           加入s1数组

3. 结果计算：

• 调用num函数处理特殊情况

• 公式计算：52 - 独特牌数

四、完整代码实现（带注释）

#include<iostream>
using namespace std;

// 去重函数：返回独特牌的数量
int bocket(string s[],int size){
    string s1[53]; // 辅助存储数组（多1位防越界）
    int s1_size = 0; // 计数器
    
    for (int i = 0;i < size;i++){
        bool once = true; // 标记是否首次出现
        // 检查是否已存在
        for (int j = 0;j < s1_size;j++)
            if (s1[j] == s[i]) once = false;
        
        if (once) { // 新牌处理
            s1[s1_size] = s[i];
            s1_size++;
        }
    }
    return s1_size;
}

// 计算缺失牌数
int num(string s[],int size) {
    if (size == 1) return 51; // 特殊边界处理
    return 52 - bocket(s,size); // 标准计算
}

int main() {
    string s[52]; // 牌堆存储
    int n;
    cin >> n;
    // 输入处理
    for (int i = 0;i < n;i++)
        cin >> s[i];
    
    cout << num(s,n); // 输出结果
    return 0;
}

五、算法总结

1. 时间复杂度：O(n²) 主要消耗在双重循环去重

2. 空间复杂度：O(n) 使用固定大小辅助数组

3. 改进方向：

• 可用哈希表优化去重效率

• 预处理牌库标准集合减少计算量

4. 竞赛技巧：

• 显式处理边界条件可避免罚时

• 固定大小数组比动态容器更安全