游戏分组 - 华为OD统一考试(C卷)

OD统一考试(C卷)

分值: 100分

题解: Java / Python / C++

alt

题目描述

部门准备举办一场王者荣耀表演赛,有 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;
}

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

#面经##秋招##春招##校招##华为#
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-23 14:18
点赞 评论 收藏
分享
07-25 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
酷酷我灵儿帅:这去不去和线不线下面说实话没啥关系
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务