华为OD机试题-表演赛游戏分组（java解法）_现在给你 10 名参与者的游戏水平评分,请你根据上述要求分队,最后输出这两组的实力

一、题目

部门准备举办一场王者荣耀表演赛，有 10 名游戏爱好者参与，分 5 为两队，每队 5 人每位参与者都有一个评分，代表着他的游戏水平。
为了表演赛尽可能精彩，我们需要把 10 名参赛者分为实力尽量相近的两队。一队的实力可以表示为这一队5名队员的评分总和。
现在给你 10 名参与者的游戏水平评分，请你根据上述要求分队最后输出这两组的实力差绝对值。
例: 10名参赛者的评分分别为 5 1 8 3 4 6 7 10 9 2，分组为(1 3 5 8 10)(2 4 6 7 9)，两组实力差最小，差值为1。有多种分法，但实力差的绝对值最小为 1。

输入

10 个整数，表示 10 名参与者的游戏水平评分。范围在 [1,10000] 之间

输出

1 个整数，表示分组后两组实力差绝对值的最小值

示例一

输入

1 2 3 4 5 6 7 8 9 10
1

输出

1
1

二、思路

这道题采用动态规划的方法，想了解动态规划可以阅读这位老哥写的。看一遍就理解：动态规划详解 - 知乎 (zhihu.com)。单看代码不难理解，但是结合题目再看就搞不懂了。直觉告诉我应该分n/2次，怎么代码分了n次。为此我画了一个树状图，一目了然。例子中数组为1、2、3、4，4次分完以后，实际只有6次符合要求。也就是说合理的分法包含在了这里面。时间复杂度是O(2^n)。

三、题解

import java.util.Scanner;

public class Main {
    static int minDiff = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] split = scanner.nextLine().split(" ");

        int[] scores = new int[split.length];

        for (int i = 0; i < split.length; i++) {

            scores[i] = Integer.parseInt(split[i]);

        }

        divide(scores, 0, 0, 0);
        System.out.println(minDiff);
    }


    public static void divide(int[] scores, int i, int sum1, int sum2) {

        if (i == scores.length ) {
            minDiff = Math.min(minDiff, Math.abs(sum1 - sum2));
            return;
        }
        divide(scores, i + 1, sum1 + scores[i], sum2);
        divide(scores, i + 1, sum1, sum2 + scores[i]);
    }

}

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

注：题目来自梦想橡皮擦