跳转至

1815. 得到新鲜甜甜圈的最多组数

题目描述

有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。

当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。

你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多 有多少组人会感到开心。

 

示例 1：

输入：batchSize = 3, groups = [1,2,3,4,5,6]
输出：4
解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。

示例 2：

输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出：4

 

提示：

  • 1 <= batchSize <= 9
  • 1 <= groups.length <= 30
  • 1 <= groups[i] <= 109

解法

方法一：贪心 + 状态压缩 + 记忆化搜索

思考

一组开心当且仅当轮到它时余下甜甜圈恰为 \(0\)，即此前人数之和能被 \(\textit{batchSize}\) 整除。组数不超过 \(30\)，穷举排列为 \(30!\)，不可行。

余数为 \(0\) 的组不影响后续，可先全部计入答案。其余组只保留对 \(\textit{batchSize}\) 的余数；每个余数至多出现 \(30\) 次，可用 \(5\) 位计数，全部余数装进一个整数 \(state\)。记忆化 \(dfs(state,mod)\) 枚举再安排一个余数，并在 \(mod=0\) 时给当前组加一分。

题目实际上要我们找到一种安排顺序，使得前缀和（这里指的是“人数”）与 \(batchSize\) 取模后为 \(0\) 的组数最多。因此，我们可以将所有顾客按组分成两类：

  • 人数为 \(batchSize\) 的整数倍的顾客，这些顾客不会对下一组顾客的甜甜圈产生影响，我们可以贪心地优先安排这些组的顾客，那么这些组的顾客都会感到开心，“初始答案”为这些组的数量；
  • 人数不为 \(batchSize\) 的整数倍的顾客，这些顾客的安排顺序会影响下一组顾客的甜甜圈。我们可以对这里每一组的人数 \(v\) 模 \(batchSize\)，得到的这些余数构成一个集合，集合中的元素值范围是 \([1,2...,batchSize-1]\)。数组 \(groups\) 的长度最大为 \(30\)，因此，每个余数的数量最大不超过 \(30\)。我们可以用 \(5\) 个二进制位来表示一个余数的数量，而 \(batchSize\) 最大为 \(9\)，那么表示这些余数以及对应的数量总共需要的二进制位就是 \(5\times (9-1)=40\)。我们可以用一个 \(64\) 位整数 \(state\) 来表示。

接下来，我们设计一个函数 \(dfs(state, mod)\)，表示安排状态为 \(state\)，且当前前缀余数为 \(mod\) 时，能使得多少组感到开心。那么我们在“初始答案”加上 \(dfs(state, 0)\)，即为最终答案。

函数 \(dfs(state, mod)\) 的实现逻辑如下：

我们枚举 \(1\) 到 \(batchSize-1\) 的每一个余数 \(i\)，如果余数 \(i\) 的数量不为 \(0\)，那么我们可以将余数 \(i\) 的数量减去 \(1\)，将当前前缀余数加上 \(i\) 并且对 \(batchSize\) 取模，然后递归调用函数 \(dfs\)，求出子状态的最优解，取最大值即可。最后判断 \(mod\) 是否为 \(0\)，如果为 \(0\)，我们在最大值上加 \(1\) 后返回，否则直接返回最大值。

过程中，我们可以使用记忆化搜索来避免状态的重复计算。

时间复杂度不超过 \(O(10^7)\)，空间复杂度不超过 \(O(10^6)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        @cache
        def dfs(state, mod):
            res = 0
            x = int(mod == 0)
            for i in range(1, batchSize):
                if state >> (i * 5) & 31:
                    t = dfs(state - (1 << (i * 5)), (mod + i) % batchSize)
                    res = max(res, t + x)
            return res

        state = ans = 0
        for v in groups:
            i = v % batchSize
            ans += i == 0
            if i:
                state += 1 << (i * 5)
        ans += dfs(state, 0)
        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
class Solution {
    private Map<Long, Integer> f = new HashMap<>();
    private int size;

    public int maxHappyGroups(int batchSize, int[] groups) {
        size = batchSize;
        int ans = 0;
        long state = 0;
        for (int g : groups) {
            int i = g % size;
            if (i == 0) {
                ++ans;
            } else {
                state += 1l << (i * 5);
            }
        }
        ans += dfs(state, 0);
        return ans;
    }

    private int dfs(long state, int mod) {
        if (f.containsKey(state)) {
            return f.get(state);
        }
        int res = 0;
        for (int i = 1; i < size; ++i) {
            if ((state >> (i * 5) & 31) != 0) {
                int t = dfs(state - (1l << (i * 5)), (mod + i) % size);
                res = Math.max(res, t + (mod == 0 ? 1 : 0));
            }
        }
        f.put(state, res);
        return res;
    }
}

 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
class Solution {
public:
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        using ll = long long;
        unordered_map<ll, int> f;
        ll state = 0;
        int ans = 0;
        for (auto& v : groups) {
            int i = v % batchSize;
            ans += i == 0;
            if (i) {
                state += 1ll << (i * 5);
            }
        }
        function<int(ll, int)> dfs = [&](ll state, int mod) {
            if (f.count(state)) {
                return f[state];
            }
            int res = 0;
            int x = mod == 0;
            for (int i = 1; i < batchSize; ++i) {
                if (state >> (i * 5) & 31) {
                    int t = dfs(state - (1ll << (i * 5)), (mod + i) % batchSize);
                    res = max(res, t + x);
                }
            }
            return f[state] = res;
        };
        ans += dfs(state, 0);
        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
func maxHappyGroups(batchSize int, groups []int) (ans int) {
    state := 0
    for _, v := range groups {
        i := v % batchSize
        if i == 0 {
            ans++
        } else {
            state += 1 << (i * 5)
        }
    }
    f := map[int]int{}
    var dfs func(int, int) int
    dfs = func(state, mod int) int {
        if v, ok := f[state]; ok {
            return v
        }
        res := 0
        x := 0
        if mod == 0 {
            x = 1
        }
        for i := 1; i < batchSize; i++ {
            if state>>(i*5)&31 != 0 {
                t := dfs(state-1<<(i*5), (mod+i)%batchSize)
                res = max(res, t+x)
            }
        }
        f[state] = res
        return res
    }
    ans += dfs(state, 0)
    return
}

方法二：记忆化搜索（按组排列）

思考

方法一只按余数个数压缩状态，实现依赖位宽约定。也可以把「尚未安排的组」直接做成二进制掩码：\(m\) 为余数非 \(0\) 的组数，\(m\le 30\) 但相同余数可去重枚举。\(dfs(state,x)\) 在掩码上选未用组，前缀余数为 \(0\) 时加分。状态数变为 \(O(2^m)\)，组很少时更直观。

先把人数为 \(batchSize\) 整数倍的组贪心计入答案，再只保留其余组对 \(batchSize\) 取模后的余数。

用二进制状态表示哪些组已经安排，设计函数 \(dfs(state, x)\)：当前已安排集合为 \(state\)、前缀余数为 \(x\) 时，还能再让多少组开心。枚举尚未安排的组，对相同余数去重后递归；若 \(x = 0\)，当前这一步会让一组开心。

时间复杂度 \(O(2^m \times m)\)，空间复杂度 \(O(2^m)\)。其中 \(m\) 为余数非 \(0\) 的组数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        @cache
        def dfs(state, x):
            if state == mask:
                return 0
            vis = [False] * batchSize
            res = 0
            for i, v in enumerate(g):
                if state >> i & 1 == 0 and not vis[v]:
                    vis[v] = True
                    y = (x + v) % batchSize
                    res = max(res, dfs(state | 1 << i, y))
            return res + (x == 0)

        g = [v % batchSize for v in groups if v % batchSize]
        mask = (1 << len(g)) - 1
        return len(groups) - len(g) + dfs(0, 0)

评论