【2024最新华为OD-C卷试题汇总】游戏表演赛分队(100分)

【2024最新华为OD-C卷试题汇总】游戏表演赛分队(100分) - 三语言AC题解(Python/Java/Cpp)

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

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

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

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

文章目录

前言
- 🎀关于华为OD
- 🧭 机试备考指南
- 🎫 游戏表演赛分队
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- ✅AC代码截图

前言

🎀关于华为OD

✨华为OD的概念
华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。

🧭 机试备考指南

华为OD的题库大半年跟新一次，也就是说，一旦跟新，那么本年用的题目就是从该题库种选题，大概有100～200道左右
最近考试换为C/D卷，C/D卷题库是一样的，D卷为双机位监控，某些外包公司应聘的为D卷。
为此清隆帮大家搜集并整理了C卷的题库，后续会由清隆的ACM银牌团队将题目整理后搬上OJ，支持在线评测。

🎫 游戏表演赛分队

问题描述

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

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

输入格式

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

输出格式

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

样例输入

1 2 3 4 5 6 7 8 9 10

样例输出

数据范围

$\leq$ 游戏水平评分 $\leq 10000$

题解

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

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

由于参赛者只有 $10$ 人，所以二进制数的数量为 $2^{10} = 1024$ ，枚举的复杂度是可以接受的。

时间复杂度 $O(2^n)$ ，其中 $n$ 为参赛人数。空间复杂度 $O (n)$ 。

参考代码

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;
    }
}

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

int solve(vector<int>& scores) {
    int n = scores.size();
    int ans = 2e9;
    
    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;
}