返回目录

题目描述

部门准备举办一场王者荣耀表演赛，有 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
说明10名队员分为两组，两组实力差绝对值最小为1

Python算法源码

# 输入获取
arr = list(map(int, input().split()))

# 算法入口
def getResult(arr):
    arr.sort()

    # 求解去重组合
    def dfs(index, level, sumV, res):
        if level == 5:  # 如果已经选取了5个数字
            res.append(sumV)  # 将当前选取的数字之和加入结果列表
            return

        while index < 10:  # 遍历数组中的数字
            if index > 0 and arr[index] == arr[index - 1]:  # 如果当前数字与前一个相同，跳过
                index += 1
                continue
            dfs(index + 1, level + 1, sumV + arr[index], res)  # 递归调用，选取下一个数字
            index += 1

    res = []
    # 使用深度优先搜索（DFS）求解10选5的去重组合，并将组合之和记录进res中
    dfs(0, 0, 0, res)

    sumV = sum(arr)
    # 计算最小实力差，某队实力为subSum，另一队实力为sum - subSum，两队实力差为 abs((sum - subSum) - subSum)
    return min(map(lambda subSum: abs(sumV - 2 * subSum), res))

# 算法调用
print(getResult(arr))

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 宏定义，获取两个值中的最小值
#define MIN(a,b) ((a) < (b) ? (a) : (b))

// 定义链表中的节点
typedef struct Node {
    int ele;            // 节点中存储的元素
    struct Node *next;  // 指向下一个节点的指针
} Node;

// 定义链表结构
typedef struct List {
    int size;   // 链表中的元素数量
    Node *head; // 指向第一个节点的指针
    Node *tail; // 指向最后一个节点的指针
} List;

// 函数原型
List *new_List();
void addLast_List(List *lst, int ele);
void dfs(int arr[], int index, int level, int sum, List *res);
int getResult(int arr[]);

// 主函数
int main() {
    int arr[10];
    // 输入数组的值
    for (int i = 0; i < 10; i++) {
        scanf("%d", &arr[i]);
    }

    // 获取并打印结果
    printf("%d\n", getResult(arr));

    return 0;
}

// qsort 的比较函数
int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

// 计算结果的函数
int getResult(int arr[]) {
    // 对数组进行排序
    qsort(arr, 10, sizeof(int), cmp);

    // 创建一个新的链表来存储结果
    List *res = new_List();
    // 进行深度优先搜索，找到 10 选 5 的唯一组合，并将每个组合的和记录在 'res' 中
    dfs(arr, 0, 0, 0, res);

    // 计算数组中所有元素的总和
    int sum = 0;
    for (int i = 0; i < 10; i++) sum += arr[i];

    // 将答案初始化为最大可能的值
    int ans = INT_MAX;

    // 遍历链表以找到力量差的最小值
    Node *cur = res->head;
    while (cur != NULL) {
        ans = MIN(ans, abs(sum - 2 * cur->ele));
        cur = cur->next;
    }

    return ans;
}

// 执行深度优先搜索以计算唯一组合
void dfs(int arr[], int index, int level, int sum, List *res) {
    // 基本情况：如果当前组合大小为 5，则将其和添加到结果链表中
    if (level == 5) {
        addLast_List(res, sum);
        return;
    }

    // 递归情况：从当前索引开始尝试所有可能的组合
    for (int i = index; i < 10; i++) {
        // 在树的同一层避免重复
        if (i > index && arr[i] == arr[i - 1]) continue;
        dfs(arr, i + 1, level + 1, sum + arr[i], res);
    }
}

// 创建一个新的链表
List *new_List() {
    // 分配链表结构的内存
    List *lst = (List *) malloc(sizeof(List));

    // 初始化链表属性
    lst->size = 0;
    lst->head = NULL;
    lst->tail = NULL;

    return lst;
}

// 将元素添加到链表末尾的函数
void addLast_List(List *lst, int ele) {
    // 创建一个新节点
    Node *node = (Node *) malloc(sizeof(Node));

    // 初始化节点属性
    node->ele = ele;
    node->next = NULL;

    // 更新链表的尾指针
    if (lst->size == 0) {
        lst->head = node;
        lst->tail = node;
    } else {
        lst->tail->next = node;
        lst->tail = node;
    }

    // 增加链表的大小
    lst->size++;
}

Java算法源码

import java.util.Scanner;
 
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.lang.Math;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        List<Integer> teamNumber = new ArrayList<>();
        int sum = 0;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            teamNumber.add(a);
            sum += a;
        }
        int result = sum;
        // System.out.println(sum);
        //可以通过sum/2 剪纸
        for(int one = 0; one < 10; one++){
            for(int two = one+1; two < 10; two++){
                int add12 = teamNumber.get(one) + teamNumber.get(two);
                for(int three = two+1; three < 10; three++){
                    int add23 = teamNumber.get(three) + add12;
                    for(int four = three+1; four < 10; four++){
                        int add34 = teamNumber.get(four) + add23;
                        for(int five = four+1; five < 10; five++){
                            int add45 = teamNumber.get(five) + add34;
                            result = Math.min(result, Math.abs(sum-add45*2));
                        }
                    }
                }
            }
        }
        System.out.println(result);
    }
}
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏