华为OD机试-MVP争夺战_mvp争夺战华为机试

题目描述

在星球争霸篮球赛对抗赛中，强大的宇宙战队，希望每个人都能拿到MVP。
MVP的条件是，单场最高分得分获得者，可以并列，所以宇宙战队决定在比赛中，尽可能让更多的队员上场，且让所有有得分的队员得分都相同。
然而比赛过程中的每一分钟的得分都只能由某一个人包揽。
输入描述： 输入第一行为一个数字t，表示有得分的分钟数（ 1 <= t <= 50），第二行为t个数字，代表每一分钟的得分p（1 <= p <= 50）
输出描述： 输出有得分的队员都是MVP时最少的MVP得分。
补充说明：
示例
示例1
输入： 9
5 2 1 5 2 1 5 2 1
输出： 6
说明： 样例解释：一共4人得分，分别都为6分
5 + 1
5 + 1
5 + 1
2 + 2 + 2

代码

class Solution {
    public int getResult(int[] values) {
        int l = values.length;
        int sum=0;
        int max=-1;
        int[] temp=new int[l];
        for(int x:values){
            sum+=x;
            max=Math.max(max,x);
        }
        int groupMax=sum/max;//最多分的组数，再大一些mvp的得分比每日的最大分数还小，不可能。
        //遍历分组数。mvp得分一定是整数，如果是小数跳过
        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)) {
                return sum/presentGrop;
            }
        }
        return -1;
    }
    /**判断能否成功分组
    *temp[i]表示value[i]在分完组后的第几组，每一个value[i]都对应一个temp[i]
    *presentGrop表示一共被分为几组，targetTotal表示每一组的和
    *groupId表示被分到第几组，属于区间[1，presentGrop]，total表示目前第groupId组里面还需要填充的值
    */
    public 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){//表示所有组都分配完成
                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;
    }

}
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