星际篮球争霸赛 java题解

要求更多人分数相同即得到mvp，要求组数presentGrop尽可能多，从大到小枚举分组数presentGrop。
对输入的分数数组进行分配，分配为presentGrop个组，用tmp[i]记录value[i]被分配到哪一组了。
判断能否成功分组：
如果当前组总分超过每组所需，失败。如果当前组总分等于每组所需，分配当前组成功。如果当前组已经是最后一组，那么返回成功。如果还有下一组，把分数数组继续分配给下一组。对于每一个未被分配的分数，尝试将该分数分给下一组，递归验证是否成功。如果成功，说明当前分组数可行（最终答案是分组数中最大的，即平均每组分数最小的）。如果不成功，取消把这个分数分配给这一组的决定，把这个分数标记为未分配。

class Solution {
    public int getResult(int[] values) {
        int l = values.length;//l代表输入得分数组的长度
        int sum = 0; //sum代表数组元素总和
        int max = -1;  //values数组中最大的元素。
        int[] temp = new int[l]; //temp[i]表示value[i]在分完组后的第几组，每一个value[i]都对应一个temp[i]
        for (int x : values) {
            sum += x;
            max = Math.max(max, x);
        }
        int groupMax = sum / max;//最多能分的组数。
        //遍历分组数。mvp得分一定是整数，如果是小数跳过
        ArrayList<Integer> mintarget = new ArrayList<Integer>();
        //mintarget列表是用来存放能分组之后的每组总分  可以分组的每组分数
        // 因为题目要求总分最小，所以最后要判断。
        Integer min = 0;
        for (int presentGrop = groupMax; presentGrop >= 1; presentGrop--) {
            if (sum % presentGrop != 0) {//每组分数不是总分的因子
                continue;
            }
            //temp[i]表示value[i]在分完组后的第几组。
            // 初始为0表示value[i]还没有被分过组，默认
            for (int j = 0; j < l; j++) {
                temp[j] = 0;
            }
            //输入的分数、分组情况、总组数、每组的分数、目前组的分数还差多少、当前是第几组
            if (judge(values, temp, presentGrop, sum / presentGrop, sum / presentGrop, 1)) {
                mintarget.add(sum/presentGrop);//可分，存放每组分数
                //如果能成功分组，那就把每次分组完后每一组的总分放到列表当中。
                min = Collections.min(mintarget);
            }
        }
        System.out.println(min);
        return -1;
    }
//   判断能否成功分组
//     temp[i]表示value[i]在分完组后的第几组，每一个value[i]都对应一个temp[i]
//     *presentGrop表示一共被分为几组，
//     targetTotal表示每一组的
//     total表示目前第groupId组里面还需要填充的值
//     groupId表示被分到第几组，属于区间[1，presentGrop]，
//
    public static boolean judge(int[] values, int[] temp, int presentGrop, int targetTotal, int total, int groupId) {
        if (total < 0) {//目前这组分数已经比需要的每组分数高了，越界了，没成功分组
            return false;
        }
        if (total == 0) {//表示第groupId组已经分配完毕
            groupId++;//需要分配下一组
            total = targetTotal;//下一组还未开始分配，需要填充的值重置为targetTotal，下一组还需要的分数
            if (groupId == presentGrop + 1) {//表示所有组都分配完成   （+1前）当前组别=总组数
                return true;
            }
        }
        //对输入的所有分数进行分配
        for (int i = 0; i < values.length; i++) {
            if (temp[i] != 0) {//表示value[i]已经分配过了，跳过
                continue;
            }
            temp[i] = groupId;//尝试分配value[i]到第groupId组
            if (judge(values, temp, presentGrop, targetTotal, total - values[i], groupId)) {//判断分配完该value[i]后能否成功分组，只需改变total的值=total-values[i]
                return true;
            }
            //如果不成功，才会跳到此步
            temp[i] = 0;//不能成功分组，把value[i]置为未分配过
        }
        return false;
    }
// main函数，Scanner方法主要是创建一个对象接收输入的数据。
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        //输入t为第一行数字，表示有得分的分钟数
        if (t < 1 || t > 50) {
            System.out.println("input error");
            return;
        }
        //scoreArray为第二行数字组成的一个数组，代表每一分钟的得分，共有t个元素
        int[] scoreArray = new int[t];
        for (int i = 0; i < scoreArray.length; ++i) {
            scoreArray[i] = scan.nextInt();
        }
        //在主函数中调用其他方法，需要先创建一个对象，然后使用对象调用方法。
        Solution solution = new Solution();
        //getResult方法判断输入的t个元素能否分组，并且每一组的总分一样。
        solution.getResult(scoreArray);

    }
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

某付费专栏的没有注释根本看不懂，搜到了一篇写的很好的
参考博文，在他的基础上加了一点点注释