华为OD机试真题【篮球比赛】

Love The Way You Lie 2023-10-12 14:06 17阅读 0赞

#### 1、题目描述 ####

**【篮球比赛】**  
一个有N个选手参加比赛，选手编号为1~N（3<=N<=100），有M（3<=M<=10）个评委对选手进行打分。  
打分规则为每个评委对选手打分，最高分10分，最低分1分。  
请计算得分最多的3位选手的编号。  
如果得分相同，则得分高分值最多的选手排名靠前  
(10分数量相同，则比较9分的数量，以此类推，用例中不会出现多个选手得分完全相同的情况)。  
**【输入描述】**  
10个篮球队员的战斗力(整数,范围\[1, 10000\])，战斗力之间用空格分隔，如:10987654321  
不需要考虑异常输入的场景。  
**【输出描述】**  
最小的战斗力差值，如:1  
**【示例1】  
【输入】**  
10 9 8 7 6 5 4 3 2 1  
**【输出】**  
说明: .  
1 2 5 9 10分为一队，3 4 6 7 8分为一队，两队战斗之差最小，输出差值1。  
备注:球员分队方案不唯一 ，但最小战斗力差值固定是1。

#### 2、解题思路 ####

该题类似于将10个数分成两组，使得两组的数和之差最小。最小战斗力从差值0开始，不满足依次增加，差值为0，即将10个战斗力之和平分给两组，若无法平分则不满足，差值增加。若满足则利用回溯算法统计满足选出5个数且之后恰好为平均值的数。

#### 3、参考代码 ####

import java.util.Arrays;
    import java.util.Scanner;
    
    /**
     * @Author 
     * @Date 2023/6/11 15:15
     */
    public class 篮球比赛 {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
        
                int[] array = Arrays.stream(in.nextLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();
    
                int totalSum = 0;
                for (int arr : array) {
        
                    totalSum += arr;
                }
    
                // 从0开始找最小差值战斗力
                for (int i = 0; i <= totalSum; i++) {
        
                    int target = (totalSum - i);
                    if (target % 2 == 0) {
          // 总和减去差值可以被平分为两组
                        if (dfs(array, 0, target / 2, new boolean[10])) {
        
                            System.out.println(i);  // 能匹配则输出
                            break;
                        }
                    }
                }
    
            }
        }
    
        // 回溯 遍历搜索分配球员
        public static boolean dfs(int[] array, int startIndex, int sum, boolean[] used) {
        
            if (startIndex > 5 || sum < 0) {
        
                return false;
            }
            if (startIndex == 5 && sum == 0) {
        
                return true;
            }
    
            for (int i = 0; i < array.length; i++) {
        
                if (used[i]) {
        
                    continue;
                }
                used[i] = true;
                if (dfs(array, startIndex + 1, sum - array[i], used)) {
        
                    return true;
                }
                used[i] = false;  // 回溯 不选
            }
            return false;
        }
    }

#### 4、相似题目 ####

（1）[代码随想录回溯算法组合题型][Link 1]

[Link 1]: https://www.programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E9%A2%98%E7%9B%AE%E5%88%86%E7%B1%BB%E5%A4%A7%E7%BA%B2%E5%A6%82%E4%B8%8B