C++ 实现：幼儿园凑队游戏，二分查找求解每队最大人数！

要解决这个问题，我们需要找到每支队伍的最大人数，使得能够组成至少 \( x \) 支队伍，并且每支队伍的所有孩子都来自同一个班级。我们可以通过二分查找来确定这个最大人数。 具体步骤如下： 1. 定义二分查找的范围： - 最小值 `low` 为 1（因为每支队伍至少有 1 个人）。 - 最大值 `high` 为所有班级中人数最多的班级的人数（因为队伍人数不能超过任何一个班级的人数）。 2. 二分查找： - 计算中间值 `mid`。 - 检查以 `mid` 为队伍人数时，是否可以组成至少 \( x \) 支队伍。 - 如果可以，则说明可以尝试更大的队伍人数，将 `low` 更新为 `mid + 1`。 - 如果不可以，则说明需要减小队伍人数，将 `high` 更新为 `mid - 1`。 3. 检查条件： - 对于每个班级，计算可以组成的队伍数，累加这些队伍数。 - 如果总队伍数大于或等于 \( x \)，则满足条件。 4. 返回结果： - 最终 `high` 的值即为每支队伍的最大人数。 下面是实现这个算法的 C++ 代码： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; bool canFormTeams(const vector<int>& classes, int teamSize, int minTeams) { int totalTeams = 0; for (int i = 0; i < classes.size(); ++i) { totalTeams += classes[i] / teamSize; } return totalTeams >= minTeams; } int main() { int n, x; cin >> n >> x; vector<int> classes(n); for (int i = 0; i < n; ++i) { cin >> classes[i]; } int low = 1; int high = *max_element(classes.begin(), classes.end()); while (low <= high) { int mid = low + (high - low) / 2; if (canFormTeams(classes, mid, x)) { low = mid + 1; } else { high = mid - 1; } } cout << high << endl; return 0; } ``` 解释 - canFormTeams 函数：检查以给定的队伍人数 `teamSize` 是否可以组成至少 `minTeams` 支队伍。 - 主函数： - 读取输入数据。 - 初始化 `low` 和 `high`。 - 使用二分查找来确定最大队伍人数。 - 输出结果。 这个算法的时间复杂度是 \( O(n \log m) \)，其中 \( n \) 是班级数，\( m \) 是最大班级人数。这对于给定的输入范围是高效的。 ######[AI写代码神器 | 640点数解答 | 2024-10-17 16:08:54]