游戏分组 - 华为OD统一考试

OD统一考试

分值： 100分

题解： Java / Python / C++

题目描述

部门准备举办一场王者荣耀表演赛，有 10 名游戏爱好者参与，分为两队，每队 5 人。

每位参与者都有一个评分，代表着他的游戏水平。为了表演赛尽可能精彩，我们需要把 10 名参赛者分为实力尽量相近的两队。

一队的实力可以表示为这一队 5 名队员的评分总和。

现在给你 10 名参与者的游戏水平评分，请你根据上述要求分队，最后输出这两组的实力差绝对值。

输入描述

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

输出描述

实力最相近两队的实力差绝对值。

示例1

输入：
1 2 3 4 5 6 7 8 9 10

输出：
1

说明：
10 名队员分为两组，两组实力差绝对值最小为 1

题解

核心是通过递归穷举所有可能的分组情况，计算两组实力之差的绝对值，最终找到实力最相近的两组。这是一种暴力穷举的方法，对于题目中给定的规模，是可行的。

此题的特点：

• 通过递归穷举分组情况。
• 利用全局变量记录最小差值。
• 对每一种分组情况计算实力差值。

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        while (scanner.hasNext()) list.add(scanner.nextInt());
        Solution solution = new Solution(list);
        solution.solve(0, 0, 0);
        System.out.println(solution.minDifference);
    }

}

class Solution {
    List<Integer> arr;
    int total, n, minDifference;

    public Solution(List<Integer> arr) {
        this.arr = arr;
        this.n = arr.size();
        this.minDifference = Integer.MAX_VALUE;
        this.total = arr.stream().mapToInt(Integer::intValue).sum();
    }

    public void solve(int idx, int selectCnt, int selectSum) {
        if (selectCnt == n / 2) {
            minDifference = Math.min(minDifference, Math.abs(total - 2 * selectSum));
            return;
        }

        for (int i = idx; i < n; i++) {
            // 不选择时
            solve(i + 1, selectCnt, selectSum);
            // 选择时
            solve(i + 1, selectCnt + 1, selectSum + arr.get(i));
        }
    }
}

Python

from math import inf

arr = list(map(int, input().split()))

# 最小差值, 全部人员总实力， 人员总数
min_difference, tot, n = inf, sum(arr), len(arr)

def solve(idx: int, select_cnt: int, select_sum: int):
    global min_difference
    if select_cnt == n // 2:  # 当全部人员选择了一半时，计算两组实力差值是否更小
        min_difference = min(min_difference, abs(tot - 2 * select_sum))
        return

    for i in range(idx, n):
        # 不选择时
        solve(i + 1, select_cnt, select_sum)
        # 选择时
        solve(i + 1, select_cnt + 1, select_sum + arr[i])


solve(0, 0, 0)

print(min_difference)

C++

#include <bits/stdc++.h>

using namespace std;

int min_difference = INT_MAX;
vector<int> arr;
int tot, n;

void solve(int idx, int select_cnt, int select_sum) {
    if (select_cnt == n / 2) {
        min_difference = min(min_difference, abs(tot - 2 * select_sum));
        return;
    }

    for (int i = idx; i < n; i++) {
        // 不选择时
        solve(i + 1, select_cnt, select_sum);
        // 选择时
        solve(i + 1, select_cnt + 1, select_sum + arr[i]);
    }
}

int main() {
    // 读取输入
    int num;
    while (cin >> num) {
        arr.push_back(num);
    }

    tot = accumulate(arr.begin(), arr.end(), 0);
    n = arr.size();

    solve(0, 0, 0);

    cout << min_difference << endl;

    return 0;
}

????华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ???? 和收藏 ?，让更多的人看到。🙏🙏🙏