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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

有一个甜甜圈商店，每批次都烤 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] <= 10⁹

# 思路

Random

# 解法

class Solution {
    int ans ;
    public int maxHappyGroups(int batchSize, int[] groups) {
        int n = groups.length;
        Random  random= new Random();
        ans = calc(groups,batchSize);
        int step = 80;
        while(step-->0){
            for(double t = 1e6;t>1e-5;t*=0.97){
                int x = calc(groups,batchSize);
                int i = random.nextInt(n);
                int j = random.nextInt(n);
                swap(groups,i,j);
                int y = calc(groups,batchSize);
                int delta = y-x;
                if(delta>0) continue;
                if(Math.exp(delta/t)>Math.random()) continue;
                swap(groups,i,j); 
            }
        }
        return ans;
    }


    void swap(int[] g,int i,int j){
        int t = g[i];
        g[i] = g[j];
        g[j] = t;
    }

    int calc(int[] g,int m){
        int n = g.length;
        int res = 0;
        for (int i = 0, s = 0; i < n; i++) {
            if (s == 0) res++;
            s = (s + g[i]) % m;
        }
        ans = Math.max(ans, 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
33
34
35
36
37
38
39
40
41
42
43

# 总结

分析出几种情况，然后分别对各个情况实现

#Java