最新华为OD机试真题-游戏表演赛分队(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 游戏表演赛分队(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🍡 游戏表演赛分队

问题描述

K小姐所在的部门准备举办一场CF表演赛，有 名游戏爱好者参与，需要分为两队，每队 人。每位参与者都有一个评分，代表着他的游戏水平。为了让表演赛尽可能精彩，需要把 名参赛者分为实力尽量相近的两队。一队的实力可以表示为这一队 名队员的评分总和。

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

输入格式

输入一行，包含 个空格隔开的整数，表示 名参与者的游戏水平评分，范围在 之间。

输出格式

输出一个整数，表示分队后两队实力差的绝对值。

样例输入

1 2 3 4 5 6 7 8 9 10

样例输出

1

数据范围

游戏水平评分

题解

本题可以通过枚举所有可能的分队方式，计算每种分队方式下两队实力差的绝对值，取最小值作为答案。

具体做法是，我们可以用一个长度为 的二进制数来表示一种分队方式， 表示分到第一队， 表示分到第二队。枚举所有的二进制数，对于每个二进制数，计算两队的实力总和，并计算它们的差的绝对值，更新答案即可。

由于参赛者只有 人，所以二进制数的数量为 ，枚举的复杂度是可以接受的。

时间复杂度 ，其中 为参赛人数。空间复杂度 。

参考代码

• Python

def solve():
    scores = list(map(int, input().split()))
    n = len(scores)
    ans = float('inf')

    for mask in range(1 << n):
        team1 = team2 = 0
        for i in range(n):
            if mask >> i & 1:
                team1 += scores[i]
            else:
                team2 += scores[i]
        
        if bin(mask).count('1') == n // 2:
            ans = min(ans, abs(team1 - team2))
    
    print(ans)

solve()

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {