n个球放入m个盒子c++

<think>嗯，这个问题看起来有点挑战性。我需要仔细理解题目要求。题目是说，张三有n个球，每个球上有一个数字ai。然后要把这n个球分到k个盒子里，每个盒子必须装至少0个球，可以有空的。每个盒子会显示一个整数x，x是盒子中不包含的最小非负整数。我们的目标是让所有盒子的x之和最大。现在要找出这个最大的可能值。 首先，我得想清楚如何分配这些球到各个盒子里，使得每个盒子的x尽可能大，然后总和最大。那x的计算方式是，每个盒子里找出最小的没出现的非负整数。例如，如果盒子里有0、1、2，那么x是3；如果有1、2，那么x是0，因为0没出现。所以，要让x尽可能大，必须让盒子里的数连续从0开始尽可能多，这样x才会大。 那怎么分配才能最大化总和呢？可能的一个策略是，尽可能让每个盒子覆盖不同的数段，从而让每个盒子的x尽可能大。比如，如果某个盒子的x是m，那么它需要包含0到m-1的所有数，并且不包含m。所以，每个这样的盒子的贡献是m，而总和就是所有盒子的m之和的最大值。 那如何构造这样的分配呢？可能需要统计每个数字的出现次数，然后根据这些次数来决定如何分配。例如，假设某个数i的出现次数是cnt[i]。如果cnt[i]大于等于k，那么每个盒子都可以分配至少一个i，这样可能有助于提高各个盒子的x值。反之，如果cnt[i]小于k，那么只能有cnt[i]个盒子可以包含i，剩下的盒子无法包含i，这可能影响它们的x值。 可能需要按照数字从小到大的顺序来处理，因为x的计算是基于连续的整数。例如，如果0的出现次数不够，那么有些盒子的x就会是0，而无法继续更高。所以，0的出现次数是关键。如果每个盒子都有一个0，那么每个盒子的x至少是1，但如果0的数量不够k个，那么无法满足，导致部分盒子的x为0。 所以，可能的步骤是： 1. 统计每个数字出现的次数，尤其是0到某个最大值之间的数字。 2. 找出对于每个数字i，如果cnt[i] >= k，那么可以保证每个盒子都有一个i，这样每个盒子的x至少是i+1。但如果i+1的出现次数是否足够呢？比如，当i=0时，如果每个盒子都有0，那么每个盒子的x至少是1。但若1的出现次数不足以覆盖所有盒子，则某些盒子的x可能停留在1，或者更高？ 可能需要逐级分析。例如： - 对于0的出现次数cnt[0]。如果cnt[0] < k，那么有k - cnt[0]个盒子无法包含0，这些盒子的x就是0。剩下的cnt[0]个盒子可能可以继续考虑更高的x值。 - 对于这些剩下的盒子，每个必须包含至少一个0。那么在这些盒子里，x的初始最小值是1。这时候要看1的出现次数是否足够这些盒子。例如，如果有m个盒子需要处理（比如m = cnt[0]），而cnt[1] >= m，那么每个盒子可以包含一个1，此时这些盒子的x至少是2。但如果cnt[1] < m，那么有m - cnt[1]个盒子无法包含足够的1，它们的x将为1。 - 这个过程可以继续下去，直到某个数字i的出现次数不足以覆盖当前剩余的盒子数量。 所以，这可能是一个贪心的过程：按从小到大的顺序处理每个数字i，计算当前剩余的盒子数，并确定每个i能为这些盒子贡献多少的x值增量。 例如，假设初始时我们有k个盒子。对于i=0： - 如果cnt[0] >= k，那么每个盒子都必须有一个0。此时，这些盒子的x至少是1。此时，剩余的可用盒子数目还是k，进入i=1的处理。 - 如果cnt[0] < k，那么有k - cnt[0]个盒子的x是0。剩下的cnt[0]个盒子需要处理i=1的情况。 对于i=1的处理： 假设当前处理的盒子数目是m（比如m = min(cnt[0], k)）。如果cnt[1] >= m，那么每个盒子都有1，此时这些盒子的x至少是2。否则，有m - cnt[1]个盒子无法包含1，它们的x将停留在1，而剩下的cnt[1]个盒子可以处理i=2的情况。 依此类推，直到处理到某个i，其中cnt[i]不足以覆盖当前剩余的盒子数目。 这样，每个i的贡献是当前的层数（比如i=0贡献0的数量）乘以该层能够处理的盒子数目，但可能这个思路需要调整。 举个例子，假设： i=0时，cnt[0]=3，k=5。那么有5-3=2个盒子的x是0。剩下的3个盒子进入i=1的处理。 i=1时，cnt[1]=2。这3个盒子需要每个至少一个1才能让x变为2。但是cnt[1]=2不够3，所以这3个盒子中有2个可以包含1，剩下的1个盒子无法包含1，所以它们的x是1。这时，这2个盒子可以进入i=2的处理，剩下的1个盒子的贡献是1。 此时，总贡献是： 未处理i=0的盒子贡献：2*0=0？ 或者可能需要重新考虑贡献的计算方式。比如，当处理i时，每个盒子的x至少是i+1，当它们的i出现足够的时候。例如，如果某个盒子在i=0时有0，那么在i=0处理时，它可能可以提升x到1。如果i=1的处理中，该盒子也包含1，那么x提升到2，依此类推。 或者，每个盒子的x是最大的i，使得对于所有j < i，该盒子中至少有一个j。所以，x的值等于i的最大值，其中0到i-1都存在。例如，如果盒子中的数字包含0,1,2，则x=3。 那么，每个盒子的x等于该盒子中缺失的最小非负整数，也就是最大的连续数+1。例如，如果盒子中的数有0,1,3，那么x=2。因此，x的值等于该盒子中0到x-1都存在，而x不存在。 因此，为了最大化总和，我们需要让每个盒子的x尽可能大。那么，如何分配球到各个盒子？ 可能的最优策略是，将尽可能多的盒子的x尽可能大。例如，将每个盒子的x尽可能大，然后总和会更大。 要实现这点，可能需要将每个盒子的x构造为最大的可能值。例如，假设有一个盒子包含0,1,2,...,m-1，但不包含m，那么x是m。这样的盒子贡献m。为了总和最大，我们希望尽可能多的盒子有较高的m值。 那么，如何分配每个数字的出现次数到各个盒子？ 对于每个数字i来说，如果它的出现次数足够多，那么每个盒子都可以有一个i。例如，当i=0时，若cnt[0] >=k，那么每个盒子都可以有一个0，这样每个盒子的x至少是1。此时，如果i=1的出现次数也 >=k，那么每个盒子可以有一个1，此时每个盒子的x至少是2。依此类推，直到某个i的出现次数不足以覆盖k个盒子。 假设在某个i，cnt[i] <当前所需的盒子数目。那么，此时可以分配cnt[i]个盒子每个有一个i，剩下的盒子无法获得i，因此这些剩下的盒子的x将停留在i。此时，这些剩下的盒子将不再参与更高i的处理。而分配到i的盒子可以继续处理i+1。 例如： 假设k=5，初始需要处理5个盒子。 i=0: cnt=3 → 有5-3=2个盒子无法获得0，它们的x=0。剩下的3个盒子进入i=1的处理。 i=1: cnt=4 → 有3个盒子需要处理，但cnt=4 >=3 → 每个盒子都分配一个1。此时，这些3个盒子的x至少是2。进入i=2的处理。 i=2: cnt=2 → 需要3个盒子，但cnt=2不够。因此，只有2个盒子获得2，剩下的1个盒子无法获得2，其x=2。剩下的2个盒子进入i=3的处理。 i=3: cnt=5 >=2 → 分配每个盒子一个3。此时，这两个盒子的x至少是4。进入i=4的处理。 i=4: cnt=1 → 需要2个盒子，但不够。所以，1个盒子得到4，其x=5，另一个盒子得不到，x=4。此时，总和计算为： 原来的2个盒子（没0）贡献0*2=0； 剩下的1个盒子在i=1处理时无法得到1吗？或者这可能之前的处理步骤可能有误。或者可能需要重新理清流程。 可能这个例子的处理总和计算如下： 处理i=0时，贡献的x是0的有2个盒子。剩下的3个盒子处理i=1，此时每个得到1，x至少是2。但具体这些盒子的x可能更高？ 或者，每个盒子的x是连续的，比如某个盒子的x等于最大的i，使得0到i-1都存在。例如，对于某个盒子，如果它包含0、1、2，则x是3。如果在i=0时，盒子有0，则在i=1时，如果有1，则x变成2，依此类推。 所以，每个盒子的x的值等于其能形成的最长连续自然数的长度。例如，盒子的数字包含0、1、2，则x=3。或者，如果盒子的数字是0、1、3，则x是2。 因此，要最大化总和，必须让每个盒子的最长连续自然数长度尽可能大。 那么，如何分配球到各个盒子？ 一种可能的策略是，将每个数字i尽可能多地分配到不同的盒子中，这样每个盒子可以得到更多的连续数。比如，对于每个i，如果它的出现次数足够多（>=当前处理的盒子数），则每个处理中的盒子都可以得到一个i。否则，只能分配到部分盒子，剩下的盒子无法得到i，它们的x将停留在当前处理阶段的i。 这可能形成一种贪心的处理方式，按i从小到大处理，并跟踪当前剩余的盒子数目。 举个例子，假设k=3，盒子数目初始是3。数字的出现次数如下： i | cnt[i] 0 | 5 → 足够分配给3盒子，所以每个盒子有0。处理后的盒子数目还是3，进入i=1的处理。 i=1 | 4 → 足够分配给3盒子，每个盒子有1。盒子数目3，进入i=2。 i=2 | 2 → 不够3。所以，只能分配2个盒子有2。剩下的3-2=1个盒子无法得到2，它们的x是2。而分配了2的2个盒子进入i=3的处理。此时，总贡献为1（当前处理i=2的阶段，剩下的1个盒子贡献2？或者该阶段的贡献是i的值乘以数目？） 或者，可能每个阶段i的处理会为每个未停止的盒子贡献i+1的值？ 或者，每个盒子的x的值等于其所在处理阶段的最大i值。例如，在某个阶段i的处理中，如果该盒子可以得到i，那么它可能继续到i+1的阶段，否则其x值为i，并且不再参与后续阶段。 因此，总和的计算方式为：对于每个i，有多少个盒子在i阶段停止，这些盒子的x是i，它们的数量乘以i，累加到总和。 例如，初始阶段i=0： - 有k个盒子需要处理。 - 如果cnt[0] >=k，那么所有盒子都获得0，进入i=1阶段。 - 否则，有k - cnt[0]个盒子无法获得0，它们的x是0，贡献总和加上 (k - cnt[0]) *0=0。剩下的 cnt[0]个盒子进入i=1阶段的处理。 在i=1阶段： - 处理m = cnt[0]个盒子。 - 如果cnt[1] >=m，则所有m个盒子获得1，进入i=2阶段。 - 否则，有m - cnt[1]个盒子无法获得1，它们的x是1，贡献总和加上 (m - cnt[1]) *1。剩下的 cnt[1]个盒子进入i=2阶段。 依此类推，直到处理到某个i阶段，其中cnt[i] <当前处理中的盒子数目m。此时，有m - cnt[i]个盒子的x是i，剩下的cnt[i]个盒子进入i+1阶段。 这样，总和的计算方式是，对于每个i，累加 (m_prev - m_current) * i。其中，m_prev是进入当前阶段的盒子数目，m_current是处理后的盒子数目（即能够分配到i的数目）。 例如，假设i=0阶段开始时m=5（k=5）： - cnt[0]=3 <5 → 5-3=2个盒子停止，贡献2*0=0。剩下的3个进入i=1阶段。 i=1阶段，m=3： - cnt[1]=2 <3 → 3-2=1个盒子停止，贡献1*1=1。剩下的2进入i=2阶段。 i=2阶段，m=2： - cnt[2]=5 >=2 → 所有盒子获得2，进入i=3阶段。 i=3阶段，m=2： - cnt[3]=0 <2 → 2-0=2盒子停止，贡献2*3=6。总和=0+1+6=7. 这样总和为7。此时，剩下的0个盒子继续处理，结束。 所以，总和的算法可以按以下步骤： 1. 统计每个i的出现次数cnt[i]。其中，i的可能范围较大，但实际处理时只需要到最大的i，使得存在i在数组中或者需要处理到某一步骤。 或者，可能存在i的取值是连续的，所以需要处理到某个最大的i，其中在处理到i时，当前处理的盒子数目m>0。 2. 初始化当前处理的盒子数目m =k。 3. 对于i从0开始递增： a. 当前i的出现次数为cnt_i = cnt[i]（如果i不存在于数组，则cnt_i=0）。 b. 如果cnt_i >=m： - 所有m个盒子都能分配到i，所以进入下一个i+1阶段，m的值不变。 c. 否则： - 有m - cnt_i个盒子无法分配到i，这些盒子的x是i。贡献为 (m - cnt_i)*i。 - 剩下的cnt_i个盒子进入下一阶段，所以新的m = cnt_i. d. 将贡献累加到总和中。 e. 如果新的m为0，则结束循环。 4. 最后，如果处理完所有i之后，仍有m>0的盒子，这些盒子的x等于最大的i+1。例如，假设处理到i_max，并且所有i_max的出现次数足够，那么这些盒子的x是i_max+1。例如，如果处理到i=5，并且所有盒子都分配了0~5，那么x是6，所以贡献是m*(i_max+1)。 或者，这可能取决于最后处理的i的情况。例如，假设所有盒子都分配到了i=0,1,2,...,t-1，那么它们的x是t。所以，当处理到i=t时，如果cnt[t] >=m，那么这些盒子继续处理i+1阶段。直到某个i，其中cnt[i] <m，此时贡献是(m - cnt[i])*i，剩下的cnt[i]进入下一阶段。或者，如果所有i都能满足cnt[i] >=m，那么最终每个盒子的x是最大的i+1，也就是无限处理下去？ 显然，不可能无限处理。例如，如果所有i都存在足够多的次数，那么每个盒子的x会是无限大，这显然不可能。所以，必须有一个最大的i，之后cnt[i]不再足够，或者处理到某个i之后，所有盒子都被处理完毕。 这可能说明，当所有i的cnt[i] >=m时，这些盒子的x等于当前i+1。例如，假设在处理到i=5时，所有盒子都能分配到5，那么它们的x是6。所以，当处理到i=5时，如果cnt[5] >=m，那么这些盒子的x是6。但根据前面的处理方式，此时m保持不变，进入i=6阶段。如果此时处理到i=6时，没有cnt[6]的存在，即cnt[6]=0，那么无法满足m个盒子，贡献是m*6，然后剩下的盒子数目为0。 所以，可能正确的处理方式是，无论i有多大，只要cnt[i]足够，就继续处理，直到某个i的cnt[i]<m，此时贡献(m - cnt_i)*i，剩下的盒子数目是cnt_i。当cnt_i=0时，贡献m*i，并且结束循环，因为剩下的盒子数目为0。 或者，可能必须遍历所有可能的i，直到某个i使得cnt[i] <m，然后处理。但如何确定i的范围呢？因为原数组中的数字可能很大，例如1e9，但此时cnt[i]对于未出现的i来说为0，所以当处理到某个i时，如果数组中没有这个i，则cnt[i]=0，此时贡献是m*i，并结束循环。 所以，算法的大致步骤是： sum =0 current_boxes =k for i from0 to ...: if current_boxes ==0: break cnt_i = count of i in the array if cnt_i >= current_boxes: current_boxes remains the same else: sum += (current_boxes - cnt_i) *i current_boxes = cnt_i 当cnt_i >=current_boxes时，处理下一个i。否则，计算贡献，并继续处理剩下的current_boxes=cnt_i。 当current_boxes变为0时，结束循环。 例如，假设原数组中的i可能不连续，那么处理到i=某个值时，比如原数组中没有i=3，那么cnt_i=0，此时当处理到i=3时，如果current_boxes>0，则贡献current_boxes*3，然后current_boxes=0，循环结束。 例如，考虑例子： 输入： n=6, k=2 数组是0,1,2,2,3,5 每个盒子的x可能是4或0，或者取决于分配方式。比如，将第一个盒子放0,1,2,2,3,5 → x=4。另一个盒子为空，x=0。总和是4+0=4。或者将两盒子各放三个球。例如，假设一个盒子放0,1,2，另一个盒子放2,3,5。第一个盒子的x是3，第二个盒子中的数字不包含0，所以x=0。总和是3+0=3。或者，如果分配方式是两个盒子各有一个0，那么每个盒子的x至少是1。然后每个盒子需要至少一个1，假设存在足够的话。 但根据前面的算法，处理过程如下： current_boxes=2，i=0: cnt[0]=1（因为数组中有1个0） 因为1 <2 → sum += (2-1)*0=0 → sum=0. current_boxes=1. i=1: cnt[1]=1 >=1 → current_boxes remains 1. i=2: cnt[2]=2 >=1 → current_boxes=1. i=3: cnt[3]=1 >=1 → current_boxes=1. i=4: 数组中没有4，cnt[4]=0 <1 → sum +=1*4=4 → sum=4. current_boxes=0 → 结束。 总和是4。这符合例子中的情况，其中一个盒子的x是4，另一个盒子的x是0。总和是4。所以算法给出的总和是4，这正确。 所以，算法是正确的。那现在需要将这个过程用C++代码实现。 现在，如何统计cnt[i]？因为数组中的元素可能很大，比如到1e9，所以不能直接用数组来统计。可以用一个哈希表或者map来统计每个i的出现次数。例如，用unordered_map或者map。 步骤： 1. 输入n、k，然后输入数组a。 2. 统计每个数字出现的次数，存入map或哈希表cnt。 3. 初始化sum=0，current_boxes=k. 4. 遍历i从0开始，直到current_boxes变为0： a. 取出cnt[i]，即该数字i的出现次数。如果i不在cnt中，则cnt_i=0. b. 如果cnt_i >= current_boxes → 不需要处理，current_boxes不变，进入下一个i. c. 否则，sum += (current_boxes - cnt_i) *i. current_boxes = cnt_i. d. 重复直到current_boxes=0. 这样，就可以得到最终的总和。 注意，i需要从0开始，逐步递增。比如，i=0,1,2,...直到处理完。 这样，问题转化为如何遍历i的值，并在每一步找到对应的cnt[i]。 例如，当处理到i=5时，即使原数组中没有5，cnt[5]视为0，此时会触发条件cnt_i <current_boxes，sum += current_boxes *i，然后current_boxes变为0，结束循环。 这样，算法的时间复杂度取决于最大的i值。例如，如果原数组中的最大数是M，则循环到i=M+1时可能就会终止。或者，如果在处理到某个i时，current_boxes变为0，则循环终止。 但是，当数组中没有i时，比如原数组中的数很大，那么i可能需要遍历到很大的值，例如1e9，这会导致超时。 例如，假设原数组中的数都是很大的，例如a的元素都是1e9，那么处理i=0时，cnt[0]=0，此时sum +=k*0=0，current_boxes=0。循环结束。此时总和是0，正确，因为每个盒子必须为空，所以每个盒子的x是0，总和是0*k=0。 所以在这种情况下，处理i=0后循环就结束了。因此，不会出现遍历到i=1e9的情况。 所以，算法的时间复杂度在大多数情况下是可以接受的。例如，当原数组中的数比较小时，i的值不会太大。而当原数组中的数很大时，可能在i=0时就处理完毕。 所以，这个算法的时间复杂度是O(max_i)，其中max_i是处理到的最大i值。但max_i最多可能到k次处理？或者更小？ 例如，假设原数组中的每个i都存在，并且每个i的出现次数等于current_boxes，那么循环会一直处理i=0,1,2,...直到current_boxes=0。例如，当current_boxes=k，每个i的cnt[i]=current_boxes-1。这会导致每次处理i时，current_boxes减少到cnt_i=current_boxes-1。例如，当k=5时，i=0时current_boxes=5，cnt_i=4 → sum +=1*0=0，current_boxes=4. i=1时，cnt_i=3 → sum += (4-3)*1=1，current_boxes=3. i=2时，cnt_i=2 → sum +=(3-2)*2=2 → sum=3. i=3时，cnt_i=1 → sum += (2-1)*3=3 → sum=6. i=4时，cnt_i=0 → sum +=1*4=4 → sum=10. current_boxes=0 → 结束. 所以，处理到i=4，此时循环次数是5次。所以，最大i的值可能到k-1左右？ 因此，该算法的时间复杂度是可接受的。 现在，代码如何实现？ 首先，用map或者unordered_map来统计cnt。例如： map<int, int> cnt; 或者，可以用一个unordered_map，因为顺序不重要，但我们需要按i的顺序处理，所以需要用循环i从0开始递增，直到current_boxes为0。 例如： 读取输入的数组，然后统计每个数的出现次数： int n, k; cin >>n >>k; vector<int> a(n); for (int i=0; i <n; ++i) { cin >>a[i]; } unordered_map<int, int> cnt_map; for (auto num : a) { cnt_map[num]++; } 然后，在循环中，对于每个i，取cnt_map[i]的值。如果i不存在，则cnt_i=0. 然后，处理逻辑： long long sum =0; int current_boxes =k; for (int i=0; ; ++i) { if (current_boxes ==0) break; int cnt_i = cnt_map.count(i) ? cnt_map[i] :0; if (cnt_i >= current_boxes) { // 所有盒子都分配到了i，继续下一轮 // current_boxes 不变 } else { sum += (current_boxes - cnt_i) * (long long)i; current_boxes = cnt_i; if (current_boxes ==0) break; } } 但是，这可能会导致无限循环，因为当cnt_i >= current_boxes时，i会一直递增。例如，当i=5，current_boxes=3，cnt[5]=4 >=3，则i会继续增加到6，此时cnt[6]可能不存在，导致cnt_i=0 < current_boxes=3，此时sum +=3*6=18，current_boxes=0，循环结束。 所以，循环中的i可以无限增加，直到current_boxes变为0。但实际中，当处理到i=某个值时，如果cnt_i < current_boxes，则current_boxes减少，可能变为0，否则继续。 这样，代码中的循环条件需要正确终止。例如，当current_boxes变为0时，break. 所以，在代码中，循环是无限的，但每次处理i后都会检查current_boxes是否为0，如果是则break. 现在，测试一下前面的例子： 例如，例子中的第一个盒子情况： 输入数组是0,1,2,2,3,5。n=6, k=2. cnt_map的内容： 0:1, 1:1, 2:2,3:1,5:1. 循环过程： i=0: current_boxes=2. cnt_i=1 <2. sum += (2-1)*0=0 → sum=0. current_boxes=1. i=1: cnt_i=1 >=1 → current_boxes remains 1. i=2: cnt_i=2 >=1 → current_boxes remains 1. i=3: cnt_i=1 >=1 → current_boxes remains 1. i=4: cnt_i=0 <1. sum +=1*4 → sum=4. current_boxes=0 → break. 总和是4，正确。 另一个例子： 输入盒子是1,2,2,3,5 →x=0. 如果k=1，n=5。此时，所有球必须放到一个盒子里。该盒子的x是0，因为缺少0。所以总和是0. 代码处理过程： current_boxes=1. i=0: cnt_i=0 <1. sum +=1*0=0. current_boxes=0 → break. 总和0，正确. 另一个例子： 盒子是0,0,1,2 →x=3. 假设k=1。此时，所有球放入一个盒子。x是3，所以总和3. 代码处理过程： current_boxes=1. i=0: cnt_i=2 >=1 → current_boxes=1. i=1: cnt_i=1 >=1 → current_boxes=1. i=2: cnt_i=1 >=1 → current_boxes=1. i=3: cnt_i=0 <1 → sum +=1*3=3 → current_boxes=0. 总和3，正确. 所以，代码是正确的。 现在，编写代码： 需要注意的是，当current_boxes可能很大，sum可能会超出int的范围，所以需要用long long类型。 代码结构大致如下： #include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } unordered_map<int, int> cnt_map; for (auto num : a) { cnt_map[num]++; } long long sum = 0; int current_boxes = k; for (int i = 0;; ++i) { if (current_boxes == 0) { break; } int cnt_i = cnt_map.count(i) ? cnt_map[i] : 0; if (cnt_i >= current_boxes) { // 无贡献，继续处理i+1 } else { sum += (long long)(current_boxes - cnt_i) * i; current_boxes = cnt_i; if (current_boxes == 0) { break; } } } cout << sum << endl; return 0; } 这样，应该可以正确处理各种情况。 再测试一个例子： 输入： n=3, k=3 数组是0,0,0. 处理过程： current_boxes=3. i=0: cnt_i=3 >=3 → current_boxes remains 3. i=1: cnt_i=0 <3 → sum +=3*1=3. current_boxes=0 → break. 总和3 → 每个盒子的x是1。因为每个盒子必须有一个0，所以每个盒子的x是1。总和3*1=3，正确。 是的，正确。 另一个例子： n=4, k=2. 数组是0,1,2,3. 处理过程： current_boxes=2. i=0: cnt=1 <2 → sum +=(2-1)*0=0 → current_boxes=1. i=1: cnt=1 >=1 → current_boxes=1. i=2: cnt=1 >=1 → current_boxes=1. i=3: cnt=1 >=1 → current_boxes=1. i=4: cnt=0 <1 → sum +=1*4=4 → sum=4. 总和是0+4=4。每个盒子的分配方式？ 假设一个盒子放入0、1、2、3 →x是4。另一个盒子为空 →x是0。总和4+0=4.或者，如果两个盒子各放入两个元素，比如一个盒子0、1，x是2；另一个盒子2、3，x是0. 总和是2+0=2<4。所以，最大总和是4，正确。 综上，代码正确。</think>要解决这个问题，我们需要将n个带有数字的球分配到k个盒子中，使得每个盒子显示的整数x之和最大。x是盒子中不包含的最小非负整数。以下是详细的解决方案： ### 方法思路 1. **问题分析**: - 每个盒子的x值取决于其包含的最小缺失非负整数。 - 目标是最大化所有盒子x值的总和。 2. **关键观察**: - 如果盒子中包含连续的整数0, 1, 2, ..., m-1，则x值为m。 - 为了最大化总和，应尽可能让每个盒子覆盖更多连续的整数。 3. **贪心策略**: - 按从小到大的顺序处理每个整数i，统计每个i的出现次数。 - 分配每个i到尽可能多的盒子，直到某个i的出现次数不足以覆盖当前盒子数。此时无法分配到i的盒子将停止，其x值为i。 ### 解决代码 ```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } unordered_map<int, int> cnt_map; for (auto num : a) { cnt_map[num]++; } long long sum = 0; int current_boxes = k; for (int i = 0;; ++i) { if (current_boxes == 0) { break; } int cnt_i = cnt_map.count(i) ? cnt_map[i] : 0; if (cnt_i < current_boxes) { sum += (long long)(current_boxes - cnt_i) * i; current_boxes = cnt_i; if (current_boxes == 0) break; } } cout << sum << endl; return 0; } ``` ### 代码解释 1. **输入处理**: - 读取输入的n（球的数量）和k（盒子的数量）。 - 读取每个球上的数字并存入数组。 2. **统计数字出现次数**: - 使用哈希表`cnt_map`统计每个数字的出现次数。 3. **贪心算法**: - 初始化当前需要处理的盒子数目`current_boxes`为k。 - 从0开始遍历每个整数i： - 若当前i的出现次数足够覆盖所有剩余盒子，继续处理下一个i。 - 若不足，则计算无法分配到i的盒子数，累加其贡献到总和，并更新剩余盒子数目。 该方法确保我们按最优方式分配每个数字，以最大化每个盒子的x值，从而得到最大总和。

<think>嗯，我现在得仔细看看这个问题。题目是说，张三有n个球，每个球上的数字是ai。他要把这些球分到k个盒子里，每个球必须放在盒子里。然后每个盒子会显示一个整数x，这个x是盒子中最小的不包含的非负整数。我们的任务是求所有盒子的x之和的最大值。需要找出怎么分这些球，使得总和最大。 首先，我得理解这个x的计算方式。比如，如果一个盒子里有0、1、3这三个数，那么x是2，因为0和1存在，但2不存在。如果盒子里的数是0、0、2，那么x是1，因为0存在，但1不存在。那这个x其实就是所谓的mex（最小未出现的非负整数）。 那问题转化为：将n个数分成k个非空集合（或者说允许盒子为空？不，题目说每个球必须放进盒子，所以盒子可以有空的吗？题目描述中说“有可能有空盒子”，所以盒子可以空。但每个球都必须放进盒子，所以所有盒子中的球的数目总和是n，可能有盒子没有球。） 但是每个盒子的x是mex。当盒子为空时，它的x是0，因为最小的非负整数未出现的就是0。那这个时候，这个盒子的贡献是0。所以我们需要尽可能地把球分配到不同的盒子，使得每个盒子的mex尽可能大，但总和最大。 那怎么才能让总和最大呢？假设我们有k个盒子，我们需要让尽可能多的盒子的mex较大，而剩下的盒子的mex较小或者为0。 那关键点在于，如何安排每个盒子中的数字，使得它们的mex之和最大。 举个例子，比如有一个盒子中的数字是0,1,2，那么mex是3。另一个盒子中的数字是0，则mex是1。总和是3+1=4。这样可能比把两个盒子合并后的mex更大吗？可能不一定，要看具体情况。 所以，我们需要找到一种分组方式，使得每个盒子的mex之和最大。这可能涉及到将某些特定数字分配到不同的盒子，从而增加每个盒子的mex值。 现在，我得想如何计算最大的总和。首先，我们需要知道每个盒子的mex如何计算。假设我们有一个集合S中的数字，那么mex是第一个未出现的非负整数。例如，集合{0,1,2}的mex是3，集合{1}的mex是0，集合{0}的mex是1，集合{0,2}的mex是1。 那为了最大化总和，我们需要尽可能让每个盒子的mex尽可能大。那应该怎么做？ 可能的方法是，尽可能让每个盒子包含连续的数，从0开始。比如，如果一个盒子包含0,1,2，那么mex是3。但如果某个盒子缺少中间的数，那么mex就会停止。比如盒子中有0和2，那么mex是1。这说明，要让mex尽可能大，每个盒子中的数必须包含从0到mex-1的所有数，且不包含mex。所以，对于每个盒子，mex的值等于该盒子中最大的连续数加1？或者不是？ 比如，假设盒子中的数是0,1,3。那最大的连续是0和1，所以最大的数是1。但mex是2，所以此时mex等于最大的连续数+1。如果盒子中的数是0,1,2，最大的连续数是2，mex是3=2+1。但是如果盒子中的数是0,2，那么最大的数是2，但mex是1。这时候最大的连续数是0，所以mex是1=0+1。这时候，mex等于最大的连续数加1。因此，这可能是一个规律：mex等于盒子中从0开始连续的最长序列的长度。例如，如果盒子中的数包含0到m-1，那么mex是m，不管是否存在更大的数。 所以，结论是，每个盒子的mex等于该盒子中0到m-1都出现的情况下m的值，否则是第一个断掉的点。例如，如果盒子中有0、0、1、3，那么mex是2，因为0和1都存在，但2不存在。 那如何最大化总和呢？假设我们有很多盒子，每个盒子的mex尽可能大。例如，如果我们有足够的0，那么我们可以将每个0分到不同的盒子里。比如，k=3，有三个0。那么每个盒子放一个0，这样每个盒子的mex是1。总和是3*1=3。但是如果将三个0放到同一个盒子，那么该盒子的mex是1，其他两个盒子为空，总和是1+0+0=1。显然，分开更好。这说明，当有多个0的时候，应该将它们分到不同的盒子，以增加总和。 类似的，如果有足够的0和1，那么可以分到不同的盒子。比如，如果有两个0和两个1，并且k=2。每个盒子放0和1，那么每个盒子的mex是2，总和是4。或者，如果每个盒子放0和1各一个，那么每个盒子的mex是2，总和是4。但如果将两个0和两个1分到三个盒子，其中两个盒子各有一个0和一个1，第三个盒子空，那么总和是2+2+0=4，同样。或者可能有其他分配方式。 因此，看来，最大的总和与每个盒子的mex的结构有关。每个盒子的mex等于该盒子中0到m-1都存在，但m不存在。因此，每个盒子的mex可能的值由该盒子中存在的数字决定。 那么，如何构造这样的盒子？ 可能的策略是： 1. 统计每个数字的出现次数。比如，count[0]是0出现的次数，count[1]是1出现的次数，以此类推。 2. 对于每个m，假设我们要构造一个盒子的mex为m，那么该盒子必须包含0到m-1的所有数字，且不包含m。或者，如果该盒子包含m，那么它的mex可能更大？ 或者，必须满足该盒子中没有m，但包含所有0到m-1。例如，如果盒子中的数字有0到m-1，并且没有m，则mex是m。如果该盒子中有m，那么要看是否包含m+1等，所以可能mex会更大？ 例如，盒子中的数字是0,1,3。此时mex是2。而该盒子中不包含2。所以，当构造一个mex为m的盒子时，必须满足盒子中包含0到m-1，并且不包含m。或者，可能不需要包含所有0到m-1？比如，如果盒子中的数字是0,0，那么mex是1。此时，m-1是0，所以是否必须包含所有0到m-1？是的，因为如果0到m-1中的任何一个数不存在，那么mex会更小。 例如，假设m=3，那么盒子必须包含0、1、2吗？如果盒子中的数字包含0、1、3，那么mex是2。此时，mex不是3，而是2，因为缺少2。因此，当想要一个盒子的mex是m时，必须满足该盒子包含0到m-1的所有数字，并且不包含m。否则，mex可能不等于m。 因此，构造mex为m的盒子的条件是： 盒子中的数必须包含所有0到m-1的数，并且不包含m。 或者，另一种情况是，当盒子中的数包含0到m-1的某些数，但不满足所有，那么mex会是更小的某个值。例如，盒子中有0和2，那么mex是1，因为缺少1。 所以，为了构造一个mex较大的盒子，必须尽可能包含较多的连续小数字。 因此，最大的总和可能由各个盒子的mex之和组成，而这些mex的构造需要尽可能利用已有的数字。 现在，问题转化为如何将这些数字分配到k个盒子，使得每个盒子的mex之和最大。 可能的策略是： 找出最大的可能的mex序列，每个盒子的mex是m_i，满足sum(m_i)最大。这些m_i必须满足，对于每个m_i，可以构造一个盒子，其mex为m_i，即该盒子必须包含0到m_i-1，且不包含m_i。或者，这可能并不完全正确，因为可能存在其他情况。 或者，另一种思路是，对于每个m，我们可以有多少个盒子的mex至少为m。因为每个盒子的mex为m时，贡献m到总和。而总和等于所有盒子的mex之和，可以分解为对于每个m≥1，有多少盒子的mex≥m。 例如，假设某个盒子的mex是3，那么它对总和的贡献是3=1+1+1（对于m=1、2、3）。所以，总和等于对于每个m≥1，统计有多少盒子的mex≥m，然后将这些数目相加。这可能更便于分析。 因此，总和等于Σ (从m=1到最大值) 有多少盒子的mex≥m。例如，如果一个盒子的mex是3，则它对m=1、2、3各贡献1，总和为3。 所以，总和可以看作是各个m≥1对应的盒子的数目之和，每个m对应的数目等于有多少盒子的mex≥m。 这可能更便于计算。例如，如果对于某个m，有t个盒子的mex≥m，则总和中的这一项是t。那么总和等于所有m≥1的t之和。 现在，问题转化为：如何选择盒子的分配方式，使得对于每个m≥1，尽可能多的盒子的mex≥m。 这可能更易处理，因为对于每个m，最大的可能的数目是min(count[0], count[1], ..., count[m-1], k)。或者说，这可能取决于各个数字的数量是否足够。 例如，对于m=1，每个盒子的mex≥1的条件是该盒子的mex至少是1，即该盒子的mex≥1意味着该盒子至少包含0。因为如果盒子中没有0，那么mex是0。所以，mex≥1的盒子数目等于有多少盒子至少包含一个0。而每个0只能被一个盒子使用吗？或者说，每个0可以被多个盒子使用吗？ 例如，假设有一个0，如果将它放入一个盒子，那么该盒子的mex≥1。如果这个0被放入多个盒子，显然不可能，因为每个球必须放在一个盒子里。哦，对，每个球必须放在且仅放在一个盒子。所以，每个0只能属于一个盒子。 所以，对于m=1，每个盒子想要mex≥1，必须包含至少一个0。而可用的0的数量是count[0]。因此，最多可以有count[0]个盒子的mex≥1。同时，总盒子数目是k。因此，对于m=1，最大的可能数目是min(count[0], k)。 同样，对于m=2，每个盒子的mex≥2的条件是，该盒子必须包含至少一个0和至少一个1。所以，这样的盒子的数目不能超过count[0]和count[1]的最小值。同时，每个这样的盒子需要消耗至少一个0和一个1。所以，最大的数目是min(count[0], count[1], k)。 对于m=3，每个盒子的mex≥3的条件是，该盒子必须包含至少一个0、一个1、一个2。所以，数目是min(count[0], count[1], count[2], ... count[m-1], k). 因此，对于每个m≥1，最大的可能的数目t_m是 min( count[0], count[1], ..., count[m-1], k )。同时，每个m对应的t_m是对于这个m来说，最多能有t_m个盒子的mex≥m。那么，总和等于总和Σ_{m≥1} t_m。但要注意，这些t_m之间可能存在依赖关系，例如，当m=2时，t_2的数目不能超过t_1的数目，因为如果盒子有mex≥2，那么它必须有mex≥1，所以这部分数目会被包含在t_1中。或者，这可能不需要，因为对于每个m，t_m是独立计算的？ 这似乎有问题。比如，假设count[0]=3，count[1]=2，k=3。那么，对于m=1，t_1=min(3,3)=3。对于m=2，t_2=min(3,2,3)=2。总和为3+2=5。但是，如果我们有3个盒子，每个盒子有0，那么其中两个盒子还有1。这样，这三个盒子的mex分别为1（盒子只有0），1+两个盒子有0和1，它们的mex是2。所以，总和是1+2+2=5。确实等于3+2=5。这说明，每个m的贡献是t_m，即有多少盒子的mex≥m。所以，总和等于Σ t_m。 因此，正确的总和等于对于每个m≥1，取t_m = min( count[0], count[1], ..., count[m-1], k )，然后将这些t_m相加，直到某个m，使得t_m=0为止。 例如，当某个m时，min(count[0], ..., count[m-1], k )=0，那么对于更大的m来说，这个值也会是0。所以，可以停止计算。 因此，算法的大致步骤是： 1. 统计每个数字的出现次数，建立一个数组cnt，其中cnt[i]是数字i出现的次数。 2. 对于每个m≥1，计算当前m对应的t_m = min( cnt[0], cnt[1], ..., cnt[m-1], k ) 3. 将所有的t_m相加，得到总和的最大值。 例如，假设我们有n=5，k=3，数字是0,0,1,1,2。那么： cnt[0]=2，cnt[1]=2，cnt[2]=1，其他cnt为0。 对于m=1，t_1=min(2,3)=2。因为此时m=1，需要cnt[0] >=t_1的盒子数。但是这里，当m=1时，t_1是min(cnt[0],k)= min(2,3)=2。所以，贡献是2. 对于m=2，t_2=min(cnt[0], cnt[1],k)=min(2,2,3)=2. 贡献2. 对于m=3，需要检查cnt[0], cnt[1], cnt[2], k。min(2,2,1,3)=1。贡献1. 对于m=4，需要检查cnt[0], cnt[1], cnt[2], cnt[3],k。因为cnt[3]=0，所以min(...)=0。停止。 总和是2+2+1=5. 这对应的分配方式是： 三个盒子中的两个盒子包含0、1、2，它们的mex是3。第三个盒子可能包含0、1，其mex是2。或者，可能分配方式不同，但总和是5。或者，可能每个盒子的mex分别为3、3、2。总和3+3+2=8？这显然与前面的结论矛盾。这说明我的思路可能有问题。 哦，这说明我的之前的分析是错误的。比如，当m=1时，t_1=2，但实际可能有3个盒子，每个盒子都有0吗？不可能，因为cnt[0]=2。所以最多只能有2个盒子包含0。所以，对于m=1，t_1=2。即只有2个盒子的mex≥1。第三个盒子的mex是0，因为它没有0。 那总和的构成是：对于m=1，贡献2（即有两个盒子的mex≥1）；对于m=2，贡献2（两个盒子的mex≥2）；对于m=3，贡献1（一个盒子的mex≥3）；对于m=4，贡献0。总和2+2+1=5。 例如，假设分配如下： 盒子1：0,1,2 → mex=3。对m=1、2、3各贡献1。 盒子2：0,1 → mex=2。对m=1、2各贡献1。 盒子3：空 → mex=0。无贡献。 总和是3（盒子1的贡献是3）+2（盒子2的贡献是2）+0=5。总和是5，与之前的计算一致。 所以这说明，前面的算法是正确的。那为什么上面的例子中总和是5？ 那这种情况下，总和等于Σ t_m是正确的。 所以，问题转化为，对于每个m≥1，计算t_m=min(cnt[0], cnt[1], ..., cnt[m-1],k)。然后总和是这些t_m的总和。 现在，如何实现这一点？ 首先，我们需要将所有的数字统计到一个数组cnt中。然后，对于每个m，从1开始，不断递增m，直到cnt[0...m-1]中的最小值等于0或者超过k，此时t_m=0，之后更大的m的t_m也为0，可以停止。 例如，假设我们有一个数组cnt，其中cnt[i]是数字i出现的次数。初始时，如果数字中没有i，则cnt[i]为0。 然后，对于每个m： t_m = min( min_{0<=i<m} cnt[i], k ) 然后，sum += t_m. 这看起来可行。但是，如何高效计算每个m的min_{0<=i<m} cnt[i]？ 这可能需要预处理或者动态维护。 例如，从m=1开始： 当m=1时，只需要看cnt[0]。t_1=min(cnt[0],k) 当m=2时，要看cnt[0]和cnt[1]的最小值，并与k取小。 当m=3时，要看cnt[0]、cnt[1]、cnt[2]的最小值，并与k取小。 以此类推。 所以，我们需要维护一个变量current_min，初始时为无穷大。然后，随着m的递增，每次将current_min与cnt[m-1]取最小值，得到新的current_min。然后，t_m=min(current_min, k)。如果current_min为0，则后续的m对应的t_m都为0，可以停止。 例如，步骤如下： 初始化current_min为无穷大，sum=0，m=1. 循环： current_min = min(current_min, cnt[m-1]) t_m = min(current_min, k) sum += t_m 如果t_m ==0，break. 否则，m +=1. 这样，时间复杂度是O(max_num),其中max_num是最大的数字。但题目中的数字可能很大，所以这可能不行。或者，我们可以处理到最大的m，其中cnt[m-1]存在。 或者，我们需要统计所有存在的数字，并找到最大的连续m使得前面的cnt都有足够的数量。 比如，假设数字中的最大数是max_a。那么，最大的m可能到max_a+1。因为比如，如果所有数都有连续的0到max_a，则m可以到max_a+1。此时，t_m = min(cnt[0], cnt[1], ..., cnt[max_a],k). 例如，若所有0到max_a的cnt都≥k，那么t_{max_a+1} =k。否则，取最小。 所以，我们需要遍历m，直到当前current_min变成0，或者超过当前k的限制。 这样，可能的实现步骤是： 统计所有数字的出现次数，放入cnt数组。假设数字的范围可能很大，所以需要处理所有存在的数字，或者用哈希表存储。或者，可能原问题中的ai的值范围不大？或者题目中给出的n可以是1e5等。 可能更好的方法是，遍历所有可能的m，直到current_min为0或者无法继续。 具体来说： 初始化current_min为无穷大。 sum=0. m=1. 循环： 如果m-1不在cnt中（即cnt[m-1]为0），则current_min=0. 否则，current_min = min(current_min, cnt[m-1]) 然后，t_m=min(current_min, k) sum +=t_m. 如果t_m==0，break. 否则，m++. 这样可以处理所有可能的m。 例如，假设原数字中没有某个数，比如没有2，那么当m=3时，m-1=2，此时current_min变为0，t_m=0，循环结束。 所以，这个方法是正确的。 现在，如何处理数字中的最大可能m？ 例如，如果所有数字都是0，那么cnt[0]=n. 此时，对于m=1，current_min=cnt[0]=n, t= min(n,k). sum +=t. 对于m=2，current_min= min(n, cnt[1])=0（因为cnt[1]=0），所以t=0。循环结束。总和是min(n,k). 此时，正确的总和是每个盒子的mex是1，如果它们都包含0。例如，k个盒子中，每个盒子有一个0，那么每个的mex是1，总和k*1= min(n,k) ×1。因为最多有min(n,k)个盒子可以有0。例如，n=5，k=3，则每个盒子放一个0，sum=3*1=3. 如果k=5，n=3，则每个盒子放一个0，sum=3*1=3。剩下的两个盒子为空，贡献0。总和3. 这与我们的方法得出的sum=min(3,5)=3，所以正确。 这说明方法是正确的。 现在，总结算法： 1. 统计每个数字的出现次数，存入哈希表或者数组cnt。 2. 初始化current_min为无穷大，sum=0，m=1. 3. 循环： a. 检查是否存在数字m-1。即，如果m-1不在cnt中或者cnt[m-1]==0，则current_min=0. b. 否则，current_min = min(current_min, cnt[m-1]). c. t_m = min(current_min, k). d. sum +=t_m. e. 如果t_m==0，break循环. f. m++. 4. 返回sum. 这样，就能得到正确的结果。 现在，如何用C++实现？ 可能的步骤： 首先，读取n和k。 然后，读取n个ai，统计它们的出现次数。可以用一个unordered_map或者数组。如果ai的范围很大，可以使用map或者unordered_map。或者，如果ai的范围不大，可以预分配一个足够大的数组。但题目中可能ai很大，所以用unordered_map更合适。 然后，初始化current_min为无穷大，sum=0，m=1. 然后循环： 对于每个m，检查m-1是否存在于cnt中，并且次数大于0。例如，如果cnt[m-1]是0或者不存在，则current_min=0。否则，current_min取min(current_min, cnt[m-1]). 然后，t_m = min(current_min, k). sum +=t_m. 如果t_m==0，break. m++. 重复直到退出循环。 例如，C++代码的大致结构： #include <iostream> #include <unordered_map> using namespace std; int main() { int n, k; cin >> n >> k; unordered_map<int, int> cnt; for (int i = 0; i < n; ++i) { int a; cin >> a; cnt[a]++; } int sum = 0; int current_min = 1e9; // 初始化为足够大的数 int m = 1; while (true) { if (cnt.find(m-1) == cnt.end() || cnt[m-1] == 0) { current_min = 0; } else { current_min = min(current_min, cnt[m-1]); } int t = min(current_min, k); sum += t; if (t == 0) break; m++; } cout << sum << endl; return 0; } 但这里有一个问题：当m=1时，m-1=0。我们需要检查cnt[0]是否存在。例如，如果输入中没有0，那么current_min为0，t=min(0, k)=0，循环结束。sum=0。这正确，因为没有盒子可以贡献任何mex≥1的值，所有盒子的mex都是0，总和0。 另一个例子： 输入： 3 2 0 0 1 则： cnt[0] =2，cnt[1]=1. m=1: current_min = min(初始值1e9, cnt[0]=2) → 2. t= min(2, 2) →2. sum=2. m=2: current_min= min(2, cnt[1]=1) →1. t= min(1,2) →1. sum=2+1=3. m=3: 检查cnt[2]，不存在，current_min=0. t=0. sum remains 3. 循环结束。输出3. 对应的正确分配是： 两个盒子： 盒子1：0,1 → mex=2. 盒子2：0 → mex=1. 总和是2+1=3. 确实正确。 另一个测试案例： 输入：5 3 0 0 1 1 2 则： cnt[0]=2, cnt[1]=2, cnt[2]=1. m=1: current_min =2. t=min(2,3)=2. sum=2. m=2: current_min= min(2, 2)=2. t=min(2,3)=2. sum=4. m=3: current_min= min(2,1)=1. t=min(1,3)=1. sum=5. m=4: 检查cnt[3]，不存在。 current_min=0. t=0. sum=5. 正确。 所以，代码是正确的。 那这个问题的解法就是这个算法。其核心思想是，对于每个m，计算有多少盒子的mex至少是m，然后将这些数目相加得到总和。每个m对应的数目是各个数字0~m-1的最小出现次数与k的较小值。当某个数字i的出现次数不足以支撑更高的m时，后续的数目就会变为0，结束循环。</think>为了解决这个问题，我们需要将球分配到盒子中，使得所有盒子显示的整数x（即最小未出现的非负整数）的和最大。以下是详细的解决方法和解释： ### 方法思路 1. **问题分析**: - 每个盒子的x值是该盒子的最小未出现的非负整数（mex）。 - 要最大化所有盒子x值的和，需要尽可能让每个盒子的mex尽可能大。 2. **关键观察**: - mex的计算依赖于盒子中数字的连续性。例如，盒子包含0,1,2则mex是3；若缺少1则mex是1。 - 为了最大化总和，需要统计每个数字的出现次数，并确定每个mex值对应的最大盒子数。 3. **算法步骤**: - **统计数字出现次数**：使用哈希表记录每个数字出现的次数。 - **逐层计算贡献**：对于每个可能的mex值m，计算有多少个盒子的mex至少为m。这个数目由当前层的最小数字出现次数和盒子数k决定。 - **累加总和**：将所有层的贡献累加得到最终结果。 ### 解决代码 ```cpp #include <iostream> #include <unordered_map> using namespace std; int main() { int n, k; cin >> n >> k; unordered_map<int, int> cnt; for (int i = 0; i < n; ++i) { int a; cin >> a; cnt[a]++; } int sum = 0; int current_min = 1e9; // 初始化为足够大的值 int m = 1; while (true) { // 检查是否存在数字 m-1 if (cnt.find(m-1) == cnt.end() || cnt[m-1] == 0) { current_min = 0; } else { current_min = min(current_min, cnt[m-1]); } int t = min(current_min, k); sum += t; if (t == 0) break; m++; } cout << sum << endl; return 0; } ``` ### 代码解释 - **统计数字出现次数**：使用`unordered_map`存储每个数字的出现次数。 - **逐层计算贡献**：从m=1开始，逐层计算每个mex值m对应的最大盒子数。`current_min`维护当前层的最小数字出现次数。 - **终止条件**：当某层的贡献为0时，后续层的贡献也为0，终止循环。 ### 相关问题