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

题目描述

leetcode 困难题

有一个甜甜圈商店，每批次都烤 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 组都会感到开心。

提示1：

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

状态压缩 + 记忆化搜索

设第 $i$ 批顾客的数量对 $batchSize$ 取模后的结果为 $mod_i$，如果 $(mod_0 + mod_1 + … + mod_i) \% batchSize = 0$ ，那么该批顾客就是开心的，也就是说其实我们只需要关心每批顾客数量对 $batchSize$ 取模后的结果即可。

于是我们可以先预处理出 $group[i] \%= batchSize$ ，这样一来 $group[i]$ 数量范围缩小到了 $1-9$ ，接着我们再对相同的 $group[i]$ 分为一组进行计数，设计数结果为 $cnt0,cnt1…cnt9$ ，并设 $si = cnt_i*i$ （这里的 $i$ 不是 $group$ 下标而是分组后的下标，也就是 $1-9$）。

设 $f(s0,s1,…s9)$ 为当 $group$ 取模分组后结果为 $s0, s1…s9$ 时能取到的最大开心组数。如上所说

如果 $(mod_0 + mod_1 + … + mod_i) \% batchSize== 0$ ，那么该批顾客就是开心的。

由此可以得出，设 最后一组 顾客为 $i$，状态转移方程为：

$$
\begin{align}
&f(s0…si…s9) = f(s0…si - i…s9)　　　　　if　(s0 + s1 + … si - i + s9) \% batchSize != 0 \\
&f(s0…si…s9) = f(s0…si - i…s9)+ 1　　　if　(s0 + s1 + … si - i + s9) \% batchSize == 0 \\
\end{align}
$$

剩下问题就是如何表示出 $s0,s1…s9$ 了，一种方法是开九维数组，过于复杂。

注意到 $1 <= groups.length <= 30$ ，也就是说 $si$ 均小于 $30$ ，我们可以用 $5$ 个二进制来存储一个 $si$，而 $s0$ 可以不处理，因为只需要将 $mod_0$ 的顾客最先处理，那么他们都是开心的，此时只需要将答案加上 $cnt_0$ 即可。所以我们总共需要 $8 * 5 = 40$ 个二进制就可以表示出状态，也就是一个 $long$ 类型。

具体求解时，可以采用记忆化搜索的方式，答案为当最后一组顾客为 $1…9$ 时所转移出来的最大值再加上 $cnt0$。

class Solution {
    private Map<Long, Integer> memo = new HashMap<>();
    private int batchSize;

    public int maxHappyGroups(int batchSize, int[] groups) {
        this.batchSize = batchSize;
        long[] cnt = new long[batchSize]; // long 数组，或者在下面移位时强转 long, 否则移位时会"溢出"
        for (int group : groups) {
            cnt[group % batchSize]++;
        }
        long mask = 0;
        for (int i = 1; i < batchSize; i++) {
            mask |= (cnt[i] << (5 * (i - 1)));
        }
        return dfs(mask) + (int)cnt[0];
    }

    private int dfs(long mask) {
        if (memo.containsKey(mask)) {
            return memo.get(mask);
        }
        int total = 0;
        for (int i = 1; i < batchSize; i++) {
            total += ((mask >> (5 * (i - 1))) & (0b11111)) * i;
        }
        int max = 0;
        for (int i = 1; i < batchSize; i++) {
            long curCnt = ((mask >> (5 * (i - 1))) & (0b11111));
            if (curCnt <= 0) {
                continue;
            }
            int pre = dfs(mask - (1L << (5 * (i - 1)))); // 注意是 1L，否则移位时会"溢出"
            if ((total - i) % batchSize == 0) {
                pre++;
            }
            max = Math.max(max, pre);
        }
        memo.put(mask, max);
        return max;
    }
}

模拟退火

另一种解法是 模拟退火 ，随机交换两个下标，当代价更优时必定接受，否则以一定概率接受，当起始温度小于终止温度时得到一个最优解。

class Solution {
    private List<Integer> groupList;
    private int n;
    private int batchSize;
    private int ans;
    private final Random r = new Random();

    public int maxHappyGroups(int batchSize, int[] groups) {
        this.batchSize = batchSize;
        groupList = Arrays.stream(groups).boxed().collect(Collectors.toList());
        n = groupList.size();
        Collections.shuffle(groupList);
        for(int i = 0; i < 35; i++){
            simulateAnneal();
        }
        return ans;
    }

    private void simulateAnneal() {
        for (double t = 500000; t > 1e-8; t *= 0.99) {
            int a = r.nextInt(Integer.MAX_VALUE) % n, b = r.nextInt(Integer.MAX_VALUE) % n;
            int start = calc();
            swap(a, b);
            int end = calc();
            double delta = start - end;
            if (Math.exp(-delta / t) > r.nextDouble()) {
                continue;
            }
            swap(a, b);
        }
    }

    private int calc() {
        int ret = 0, pre = 0;
        for (int i = 0; i < n; i++) {
            if(pre == 0){
                ret++;
            }
            int cur = groupList.get(i);
            if(cur < pre){
                pre -= cur;
                continue;
            }
            cur = (cur - pre) % batchSize;
            pre = cur == 0 ? 0 : batchSize - cur;
        }
        ans = Math.max(ans, ret);
        return ret;
    }


    private void swap(int a, int b) {
        if (a == b) return;
        groupList.set(a, groupList.get(a) ^ groupList.get(b));
        groupList.set(b, groupList.get(a) ^ groupList.get(b));
        groupList.set(a, groupList.get(a) ^ groupList.get(b));
    }

}