Readme

2910.Minimum-Number-of-Groups-to-Create-a-Valid-Assignment

我们首先将所有元素的频率收集起来放入一个数组arr。本题就是将arr里的每个元素都做拆分，要求最多只能拆分出两种相邻的数字（记做k和k-1）。求最少能拆分出多少个数字来。

本题的一个坑就是二分搜索是不成立的。这是说拆分的越多就越容易，这里没有单调性。比如说，[10,20]可以拆分出k=10, 即[10,10,10]；但不能拆分出k=9；但是又可以拆分出k=5，即[5,5,5,5,5,5].

本题的解法其实就是暴力尝试。假设arr的长度是n，出现最小的频次是m，那么我们就从k=m+1,m,...,1逐个尝试，找到最大的k使得所有arr的元素都能成功拆分成若干个k或k-1的和。这样的时间复杂度看上去是0(mn). 事实上mn有制约关系，如果nums的种类各不相同，那么m就是1，n就是1e5；如果nums的种类完全相同，那么m就是1e5，n就是1. 事实上，o(mn)就是1e5数量级。

接下来我们考虑，如果给定了k，如何判定某个arr的元素x能成功拆封成若干个k或k-1之和？我们将x尽量拆分出最多的k来，得到q = x/k个group，以及余数r = x%k. 此时我们还差k-r才能凑出一个k。如果k-r<=q+1，意味着我们从之前的这些group里各自都拆借1加到最后一个“落单”的group，而那些变动的group里含有的元素就是k-1，依然符合要求. 注意，如果r==0时，需要另外处理这个corner case。

最终当我们找到最大的k，使得所有arr的x都能成立时，我们用ceil(x*1.0/k)即可计算出总共分成的group的数目。