leetcode_2910 合法分组的最少组数

1. 题意

给定一组数。将这些数进行分组，使得

1. 组内所有元素相等
2. 任意两个组的大小相差不超过1

合法分组的最少组数

2. 题解

直接引用别人的题解算了吧，是一个数学变换的题。

核心是当$\lfloor \frac{v}{k}\rfloor \ge v\%k$时，$v$一定可以分为$k$和$k+1$的组。

且此时分得的组数最少为$\lceil \frac{v}{k+1}\rceil$

首先统计$nums$，得到数组$arr$。题目要求找到一个分组基准$d$，使得$arr$的每个元素可以由若干个$d$和$d+1$组成。对于元素$a$，假设$a=xd+y(d+1)a=xd+y(d+1)a=xd+y(d+1)$满足分组条件，变形得$a=(x+y)d+ya=(x+y)d+ya=(x+y)d+y$。另设$a=pd+r$，其中$p=a//d,r=a\%d$。则$a$可以写成$a=(p-k)d+(kd+r)$。式子联立得$p-k=x+y\ge y=kd+r$，因此满足分组条件的充要条件是$p-k\ge kd+r$。注意到当$k=0$时，$p-k$最大，$kd+r$最小。因此只需要$p\ge r$即可满足分组条件。
要求的最优解是$x+y=p-k$的最小值。由$p-k\ge kd+r$得$k\le (p-r)//(d+1)$，因此最优解为$p-((p-r)//(d+1))$

• 代码

class Solution {
public:



    int minGroupsForValidAssignment(vector<int>& nums) {
        

        // 3 2 3 2 3
        // 333 22 

        // 10 10 10 3 1 1
        // 11 1010 10 3

        unordered_map<int,int> um;
        for (auto &v : nums)
            um[v]++;
        vector<int> g;
        for (auto &[k, v]: um)
            g.push_back(v);
        
        sort(g.begin(), g.end() );

        int ans = 0;
        for (int d = g[0]; d >  0; --d) {
            
            ans = 0;
            for ( auto &v: g) {

                int r = v % d ;
                if ( v / d < r) {
                    ans = 0; break;
                }
                
                ans += (v + d)/(d + 1); 
            
            }
            if (ans)
                break;
        }



        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

3. 引用

03xf
云飘飘
Jacky