题解

关于：
$为什么分得的组数是：\lceil\frac{cnt[x]}{(k + 1)}\rceil$
例如
9 / 2 = 4 … 1 -> 2 2 2 2 1
9 / 3 = 3 … 0 -> 3 3 3
可看成，先把1放入2 -> 3 2 2 2
再把2放入2 -> 3 3 3
$\lceil\frac{cnt[x]}{(k + 1)}\rceil = \lfloor\frac{cnt[x] + k}{k + 1}\rfloor = (cnt[x] + k) / (k + 1)$

C++ 代码

class Solution {
public:
    int minGroupsForValidAssignment(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for(auto x : nums) cnt[x]++;
        int k = min_element(cnt.begin(), cnt.end(), [](auto& a, auto& b){
            return a.second < b.second;
        })->second;//找到map中value最小的

        while(true){
            int ans = 0;
            for(auto item : cnt){
                int x = item.second;
                if(x / k < x % k){ //当无法将多出来的余数分配到前面几个数时
                    ans = 0;
                    break;
                }
                ans += (x + k) / (k + 1);//分得组数直接就是这个
            }
            if(ans){
                return ans;
            }
            k--;
        }
    }
};