当前位置:   article > 正文

【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【回溯】2023C-表演赛游戏分组【欧弟算法】全网注释最详细分类最全的华为OD真题题解_华为odc语言笔试题

华为odc语言笔试题

题目描述与示例

题目描述

部门准备举办一场王者荣耀表演赛,有 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 2 3 4 5 6 7 8 9 10
  • 1
输出
1
  • 1
说明

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

解题思路

两队的总评分total_sum是确定的。将问题转化为,在10个元素中挑选出5个元素,使得这5个元素的和尽可能接近total_sum的一半即total_sum // 2

假定元素和较小的那组为A组,较大的那组为B组,由于sum(A) <= total_sum // 2 <= sum(B)始终成立,因此可以只考虑小于等于total_sum // 2A组情况即可。

10个元素中挑选出5个元素的组合问题,很容易想到直接使用回溯来解决。由于只考虑A组情况,所以当发现path_sum > total_sum // 2时,可以进行剪枝操作。

当然背包dp也可以解决这个问题,感兴趣的同学可以自己尝试一下。

代码

Python

# 题目:【回溯】2023C-表演赛游戏分组
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:回溯
# 代码看不懂的地方,请直接在群上提问


nums = list(map(int, input().split()))

# 所有人的评分和
total_sum = sum(nums)
# 评分和的一般,作为目标值
target = total_sum // 2

# 初始化答案为一个很大的值
ans = total_sum

def dfs(nums, path_sum, path_len, startIdx, target):
    global ans
    # 如果当前所选的人的评分已经超过了target,进行剪枝,直接返回
    if path_sum > target:
        return
    # 当恰好选择了5个数的时候,更新答案
    # B组的评分和为 total_sum - path_sum,
    # B组和A组的评分和绝对差为 
    # total_sum - path_sum - path_sum = total_sum - 2 * path_sum
    if path_len == 5:
        ans = min(ans, total_sum - 2 * path_sum)
        return
    # 横向遍历,下标从startIdx开始选择
    for i in range(startIdx, 10):
        # 下一层递归在i+1的位置开始选择
        dfs(nums, path_sum + nums[i], path_len+1, i+1, target)

# 递归入口
dfs(nums, 0, 0, 0, target)
print(ans)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

Java

import java.util.Scanner;

public class Main {

    static int totalSum = 0;
    static int ans = Integer.MAX_VALUE;

    public static void dfs(int[] nums, int pathSum, int pathLen, int startIdx, int target) {
        if (pathSum > target) return;
        if (pathLen == 5) {
            ans = Math.min(ans, totalSum - 2 * pathSum);
            return;
        }
        for (int i = startIdx; i < 10; ++i) {
            dfs(nums, pathSum + nums[i], pathLen + 1, i + 1, target);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums = new int[10];
        for (int i = 0; i < 10; ++i) {
            nums[i] = scanner.nextInt();
            totalSum += nums[i];
        }
        int target = totalSum / 2;
        dfs(nums, 0, 0, 0, target);
        System.out.println(ans);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

C++

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

int total_sum = 0;
int ans = INT_MAX;

void dfs(vector<int>& nums, int path_sum, int path_len, int startIdx, int target) {
    if (path_sum > target) return;
    if (path_len == 5) {
        ans = min(ans, total_sum - 2 * path_sum);
        return;
    }
    for (int i = startIdx; i < 10; ++i) {
        dfs(nums, path_sum + nums[i], path_len + 1, i + 1, target);
    }
}

int main() {
    vector<int> nums(10);
    for (int i = 0; i < 10; ++i) {
        cin >> nums[i];
        total_sum += nums[i];
    }
    int target = total_sum / 2;
    dfs(nums, 0, 0, 0, target);
    cout << ans << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

时空复杂度

时间复杂度: O ( 5 × C 10 5 ) O(5×C_{10}^5) O(5×C105)。状态树的高度为5,叶节点数目最多为 C 10 5 C_{10}^5 C105

空间复杂度: O ( 1 ) O(1) O(1)。最多5层递归,编译栈占用情况视为常数级别空间复杂度。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/194741
推荐阅读
相关标签
  

闽ICP备14008679号