最新华为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) {
        Scanner sc = new Scanner(System.in);
        int[] scores = new int[10];
        for (int i = 0; i < 10; i++) {
            scores[i] = sc.nextInt();
        }
        
        int ans = solve(scores);
        System.out.println(ans);
        sc.close();
    }
    
    private static int solve(int[] scores) {
        int n = scores.length;
        int ans = Integer.MAX_VALUE;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            int team1 = 0, team2 = 0;
            for (int i = 0; i < n; i++) {
                if ((mask >> i & 1) == 1) {
                    team1 += scores[i];
                } else {
                    team2 += scores[i];
                }
            }
            
            if (Integer.bitCount(mask) == n / 2) {
                ans = Math.min(ans, Math.abs(team1 - team2));
            }
        }
        
        return ans;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int solve(vector<int>& scores) {
    int n = scores.size();
    int ans = INT_MAX;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        int team1 = 0, team2 = 0;
        for (int i = 0; i < n; i++) {
            if ((mask >> i & 1) == 1) {
                team1 += scores[i];
            } else {
                team2 += scores[i];
            }
        }
        
        if (__builtin_popcount(mask) == n / 2) {
            ans = min(ans, abs(team1 - team2));
        }
    }
    
    return ans;
}

int main() {
    vector<int> scores(10);
    for (int i = 0; i < 10; i++) {
        cin >> scores[i];
    }
    
    int ans = solve(scores);
    cout << ans << endl;
    
    return 0;
}