E卷-刷题笔记合集🔗

问题描述

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

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

输入格式

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

输出格式

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

样例输入

1 2 3 4 5 6 7 8 9 10

样例输出

1

数据范围

游戏水平评分

题解

二进制枚举

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

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

由于参赛者只有 人，所以二进制数的数量为 ，枚举的复杂度是可以接受的。

时间复杂度 ，其中 为参赛人数。空间复杂度 。

参考代码

• Python

def solve():
    # 读取输入的10个评分
    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:  # 如果第i位是1，分到第一队
                team1 += scores[i]
            else:  # 否则分到第二队
                team2 += scores[i]
        
        # 如果当前分队方式恰好每队5人
        if bin(mask).count('1') == n // 2:
            # 更新答案，取最小的实力差
            ans = min(ans, abs(team1 - team2))
    
    print(ans)

solve()

• C

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

// 计算二进制数中1的个数
int count_bits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// 求两个数的绝对值差
int abs_diff(int a, int b) {
    return a > b ? a - b : b - a;
}

int solve(int scores[], int n) {
    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 & (1 << i)) {  // 如果第i位是1，分到第一队
                team1 += scores[i];
            } else {  // 否则分到第二队
                team2 += scores[i];
            }
        }
        
        // 如果当前分队方式恰好每队5人
        if (count_bits(mask) == n / 2) {
            // 更新答案，取最小的实力差
            int diff = abs_diff(team1, team2);
            if (diff < ans) {
                ans = diff;
            }
        }
    }
    
    return ans;
}

int main() {
    int scores[10];
    // 读取输入的10个评分
    for (int i = 0; i < 10; i++) {
        scanf("%d"