题目描述

部门准备举办一场王者荣耀表演赛，有 $10$ 名游戏爱好者参与，分为两队，每队 $5$ 人。每位参与者都有一个评分，代表着他的游戏水平。为了表演赛尽可能精彩，我们需要把 $10$ 名参赛者分为实力尽量相近的两队。最终输出这两组的实力差绝对值。

思路

1. 问题分析：给定 $10$ 个评分，我们需要将其分为两组，每组 $5$ 人，求两组评分和的绝对差值最小。这个问题可以看作一个组合问题，类似于分割问题。

2. 状态转移：我们可以通过遍历所有可能的 $5$ 人组合来寻找实力差最小的分组。由于组合数较小（$10$ 个人选 $5$ 个人），我们可以用位掩码（bitmask）来表示每一种组合。

3. 实现步骤：

   • 遍历 $0$ 到 $1023$（$2^{10}-1$），用二进制表示选择的 $5$ 人。
   • 计算选中队员的总评分。
   • 计算另一队的评分（总评分 - 选中队员的总评分），并计算两者的绝对差值。
   • 记录下最小的绝对差值。

代码分析

1. 输入处理：使用 std::vector<int> 存储 $10$ 个评分，通过循环读取输入。

2. 计算总和：使用 std::accumulate 计算所有评分的总和。

3. 组合遍历：利用位掩码遍历 $2^{10}$ 种可能的组合，通过 __builtin_popcount 判断当前组合中选中的人数是否为 $5$。

4. 评分和计算：计算选中队员的总评分和对立队员的总评分，更新最小差值。

5. 输出结果：打印最小绝对差值。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>  // 添加此行
#include <climits>

int main() {
    std::vector<int> scores(10);
    for (int i = 0; i < 10; ++i) {
        std::cin >> scores[i];
    }

    int total_sum = std::accumulate(scores.begin(), scores.end(), 0);
    int min_difference = INT_MAX;

    for (int mask = 0; mask < (1 << 10); ++mask) {
        if (__builtin_popcount(mask) == 5) {  // 只考虑选择5个人的组合
            int team_sum = 0;
            for (int i = 0; i < 10; ++i) {
                if (mask & (1 << i)) {
                    team_sum += scores[i];
                }
            }
            int other_team_sum = total_sum - team_sum;
            min_difference = std::min(min_difference, std::abs(team_sum - other_team_sum));
        }
    }

    std::cout << min_difference << std::endl;
    return 0;
}

python

def main():
    scores = list(map(int, input().split()))  # 输入10个评分
    total_sum = sum(scores)  # 计算总评分
    min_difference = float('inf')  # 初始化最小差值

    # 遍历所有可能的组合
    for mask in range(1 << 10):
        if bin(mask).count('1') == 5:  # 只考虑选择5个人的组合
            team_sum = sum(scores[i] for i in range(10) if mask & (1 << i))  # 计算选中队员的总评分
            other_team_sum = total_sum - team_sum  # 另一队的评分
            min_difference = min(min_difference, abs(team_sum - other_team_sum))  # 更新最小差值

    print(min_difference)  # 输出最小差值

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class TeamDivision {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] scores = new int[10];

        // 输入10个评分
        for (int i = 0; i < 10; i++) {
            scores[i] = scanner.nextInt();
        }

        int totalSum = 0;
        for (int score : scores) {
            totalSum += score;  // 计算总评分
        }

        int minDifference = Integer.MAX_VALUE;  // 初始化最小差值

        // 遍历所有可能的组合
        for (int mask = 0; mask < (1 << 10); mask++) {
            if (Integer.bitCount(mask) == 5) {  // 只考虑选择5个人的组合
                int teamSum = 0;

                for (int i = 0; i < 10; i++) {
                    if ((mask & (1 << i)) != 0) {
                        teamSum += scores[i];  // 计算选中队员的总评分
                    }
                }

                int otherTeamSum = totalSum - teamSum;  // 另一队的评分
                minDifference = Math.min(minDifference, Math.abs(teamSum - otherTeamSum));  // 更新最小差值
            }
        }

        System.out.println(minDifference);  // 输出最小差值
    }
}

题目内容

部门准备举办一场王者荣耀表演赛，有 $10$ 名游戏爱好者参与，分为两队，每队 $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

输入

1 2 3 4 5 6 7 8 9 10

输出

1

说明

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