牛客对应题目链接：分组 (nowcoder.com)
一、分析题目
1、暴力枚举
从小到大枚举所有可能的最大值，找到第⼀个符合要求的最大值。
- 统计出每一种声部的人数：hash。
- 枚举最终的分配结果中，最多的人数（x），从小到大枚举 1~hmax
2、二分优化枚举
利用二段性，⼆分出符合要求的最大值。
二、代码
1、方法一（暴力枚举）
#include <iostream> #include <unordered_map> using namespace std; int n, m; unordered_map<int, int> cnt; // 统计每种声部的⼈数 bool check(int x) // 判断最多⼈数为 x 时，能否分成 m 组 { int g = 0; // 能分成多少组 for(auto& [a, b] : cnt) { g += b / x + (b % x == 0 ? 0 : 1); } return g <= m; } int main() { cin >> n >> m; int hmax = 0; // 统计声部最多的⼈数 for(int i = 0; i < n; i++) { int x; cin >> x; hmax = max(hmax, ++cnt[x]); } int kinds = cnt.size(); if(kinds > m) // 处理边界情况 { cout << -1 << endl; } else { // 暴⼒枚举 for(int i = 1; i <= hmax; i++) // 枚举所有的最多⼈数 { if(check(i)) { cout << i << endl; break; } } } return 0; }
2、方法二（二分）
#include <iostream> #include <unordered_map> using namespace std; int n, m; unordered_map<int, int> cnt; // 统计每种声部的⼈数 bool check(int x) // 判断最多⼈数为 x 时，能否分成 m 组 { int g = 0; // 能分成多少组 for(auto& [a, b] : cnt) { g += b / x + (b % x == 0 ? 0 : 1); } return g <= m; } int main() { cin >> n >> m; int hmax = 0; // 统计声部最多的⼈数 for(int i = 0; i < n; i++) { int x; cin >> x; hmax = max(hmax, ++cnt[x]); } int kinds = cnt.size(); if(kinds > m) // 处理边界情况 { cout << -1 << endl; } else { // ⼆分解法 int l = 1, r = hmax; while(l < r) { int mid = (l + r) / 2; if(check(mid)) r = mid; else l = mid + 1; } cout << l << endl; } return 0; }
三、反思与改进
这道题的暴力枚举思路基本正确，也想到了如何去分组才是正确的，不过没有理清楚在什么样的情况下会输出 -1 以及如何 +1 个分组的写法。虽然这道题目的暴力解法可以通过，但还是需要掌握二分优化的写法，发现自己虽然会写二分，但是对于二分的运用还是没有什么思路上的框架，下次遇到需要 check 的题目就往二分上想一想，看看能不能找出其中的二段性。
