P2800. 集五福

解题思路

一共有五种不同的福卡，假设我们按照在长度等于 5 的字符串中的索引给这些福卡编号，即分别有 0、1、2、3、4 一共 5 种福卡。我们直接统计整个团队中，每种福卡的个数，而能够凑齐的福卡的套数，由数目最少的那一种福卡的数目来决定。

为了统计每一种福卡的个数，我们既可以使用哈希表来完成，也可以使用一个长度为 5 的列表来完成。这两种计数方式没有本质区别。

本题显然也是哈希表在 统计元素频率 类型的题目中的典型应用。

代码

代码一

用哈希表进行统计：

思路展开

参考代码把“凑齐多少套五福”转化成一个按位计数的问题。每个成员的福卡状态是长度为 5 的 01 字符串，第 i 位为 '1' 表示拥有第 i 种福卡，所以代码用哈希表 cnt 以位置下标 i（0 到 4，对应五种福卡）作为键，遍历每个成员的字符串，遇到 '1' 就给对应下标的计数加一。全部统计完后，cnt 中每个值就是全组拥有的该种福卡总张数。能凑成的完整套数受最稀缺的那种福卡限制：每凑一套五种福卡各出一张，所以答案就是五个计数中的最小值，代码用一趟遍历求出 minCnt 并输出。另外有一个重要分支：如果 cnt.size() 小于 5，说明至少有一种福卡全组一张都没有（该下标从未被写入哈希表），一套也凑不齐，直接输出 0。这个判断必须放在取最小值之前，因为缺失的福卡根本不会出现在 cnt 里，直接取最小值会把答案高估。

复杂度分析

设小组人数为 p（题面约定不超过 10 人），每人的福卡字符串长度固定为 5。统计阶段外层遍历 p 个成员、内层扫描 5 个字符，是 O(5p)；随后在至多 5 个键上取最小值是 O(5)。总时间 O(p)，在本题规模下相当于常数。空间上哈希表最多存 5 个键值对，为 O(1)。