ARST打卡第194周[194/521]

 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/*
感觉像是让groups里面的数字取模batchSize后，凑成batchSize的倍数，
然后小的放前面，大的放后面，尽量让更多的组员开心。
但是凑数需要找规律...二元组合好像需要用什么操作来着，有点忘了，看看题解

a1,a2...an是0,1,⋯,n−1 的元素的**个数**

看题解也看了半天，确实是2023大年初一的hard...继续加油吧，嗯嗯
*/
func maxHappyGroups(batchSize int, groups []int) (ans int) {
    const kWidth = 5
    const kWidthMask = 1<<kWidth - 1

    cnt := make([]int, batchSize)
    for _, x := range groups {
        cnt[x%batchSize]++
    }

    start := 0
    for i := batchSize - 1; i > 0; i-- {
        start = start<<kWidth | cnt[i]
    }

    memo := map[int]int{}
    var dfs func(int) int
    dfs = func(mask int) (best int) {
        if mask == 0 {
            return
        }
        if res, ok := memo[mask]; ok {
            return res
        }

        total := 0
        for i := 1; i < batchSize; i++ {
            amount := mask >> ((i - 1) * kWidth) & kWidthMask
            total += i * amount
        }

        for i := 1; i < batchSize; i++ {
            amount := mask >> ((i - 1) * kWidth) & kWidthMask
            if amount > 0 {
                result := dfs(mask - 1<<((i-1)*kWidth))
                if (total-i)%batchSize == 0 {
                    result++
                }
                best = max(best, result)
            }
        }
        memo[mask] = best
        return
    }
    return dfs(start) + cnt[0]
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}