P3811. 并列最高分人数

解题思路

本题和 经典题型（划分 K 个相等的子集，回溯解法）几乎是同一个题目。

强烈建议先看一下上一个题目的详细解法。

在本题中，题目并不是直接给一个 k 让我们判断是否能够将所有数字 nums 分配到 k 个桶中，而是让我们找到这个 k 并且计算出每个桶的和 per 作为答案。

所以我们仅需做一点细微的修改：从数组长度 n 开始逆序遍历 k，对于每一个 k 都去计算这个 k 能否满足条件。一旦找到这个 k 是满足题目要求的条件，说明找到了一个最大的 k，与之对应的 per 也就是能够找到的最小的 per。

另外，由于子问题本身并不具备二段性（比如说，可能存在 k=2 和 k=4 可以满足条件，但是 k=3 并不满足条件的情况），所以本题关于 k 的寻找，不适合使用二分查找来完成。

思路展开

• 代码先读入 n 个得分并从大到小排序，大的数先入桶能更早触发「桶超出 per」的判断而被剪掉，减少无效搜索。
• 主流程从 k = n 开始逆序枚举「有得分的成员数」k：k 越大，每人的得分 per = total / k 越小，也就让尽可能多的成员并列拿到最佳贡献奖。第一个可行的 k 就是最大可行值，直接输出对应的 per 并退出循环。
• 对每个 k，can_partition_k_subsets 先做两道快速筛：总分 total 不能被 k 整除，或最大单项得分 nums[0]（排序后的首元素）已经超过 per，都直接判不可行。
• 通过筛选后交给回溯函数 dfs：按下标 i 依次把第 i 个得分放进 k 个桶中的某一个，只有放入后桶内和 group[j] 不超过 per 才继续递归处理下一个数；当 i == n 说明全部得分都放完了，找到一种均分方案，把全局变量 ans 置为 True。
• 「当前桶的和与前一个桶相等就跳过」是关键剪枝：两个和相同的桶互换是等价方案，只试其中一个即可，避免大量重复搜索。
• 正文已说明 k 不具备二段性（k=2、k=4 可行不代表 k=3 可行），所以只能从大到小逐个试，不能二分；而 k = 1（所有得分归同一人）必然可行，因此循环一定能输出答案。

复杂度分析 设 n 为得分的个数。对固定的 k，dfs 最坏情况下要为 n 个数各尝试 k 个桶，时间为 O(k^n)；等和桶剪枝、per 上限剪枝与逆序排序会大幅压缩实际分支，但最坏复杂度仍是指数级。外层还要对 k 从 n 到 1 逐个尝试，以最大的 k = n 计，最坏总时间为 O(n · n^n) 量级。空间上，桶数组 group 占 O(k)，递归深度最多为 n，总辅助空间 O(n + k)；开头的排序 O(n log n) 相比之下可忽略。