【华为OD-E卷 - 87 求最多可以派出多少支团队 100分（python、java、c++、js、c）】

【华为OD-E卷 - 求最多可以派出多少支团队 100分（python、java、c++、js、c）】

题目

用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N，每个团队可以由1人或者2人组成，且1个人只能参加1个团队，计算出最多可以派出多少只符合要求的团队

输入描述

  • 第一行代表总人数，范围1-500000 第二行数组代表每个人的能力 数组大小，范围1-500000 元素取值，范围1-500000 第三行数值为团队要求的最低能力值，范围1-500000

输出描述

  • 最多可以派出的团队数量

用例

用例一：
输入：
5
3 1 5 7 9
8
  • 1
  • 2
  • 3
输出：
3
  • 1
用例二：
输入：
7
3 1 5 7 9 2 6
8
  • 1
  • 2
  • 3
输出：
4
  • 1
用例三：
输入：
3
1 1 9
8
  • 1
  • 2
  • 3
输出：
1
  • 1

python解法

  • 解题思路：
  • 这段代码的任务是根据输入的人员数量、能力值以及组成团队所需的能力值，计算可以组成的团队数量。具体规则如下：

如果某人的能力值大于等于所需的能力值 required_cap，则该人可以单独组成一个团队。
如果某两人的能力值之和大于等于 required_cap，他们可以组成一个团队。
输出满足以上条件的团队总数。
实现步骤：

将能力值分为两组：单独可以组成团队的 (solo_teams) 和需要配对的 (remaining)。
对于需要配对的成员，按照能力值从小到大排序，使用双指针方法，从两端开始配对，如果配对成功（两人能力值之和大于等于 required_cap），则计入团队，更新指针。
最后统计单独组队的人数和配对成功的团队数量，返回总数

def calculate_teams(count, abilities, required_cap):
    # 单独可以组成团队的成员（能力值大于等于 required_cap）
    solo_teams = [x for x in abilities if x >= required_cap]
    
    # 筛选出需要配对的成员（能力值小于 required_cap）
    remaining = sorted([x for x in abilities if x < required_cap])
    paired = []  # 存储成功配对的成员对

    # 双指针初始化
    i, j = 0, len(remaining) - 1

    # 使用双指针寻找可以配对的成员
    while i < j:
        # 如果最小值和最大值之和大于等于 required_cap，可以配对
        if remaining[i] + remaining[j] >= required_cap:
            paired.append((remaining[i], remaining[j]))
            i += 1  # 左指针右移
            j -= 1  # 右指针左移
        else:
            i += 1  # 如果当前最小值与最大值无法配对，尝试下一个最小值

    # 返回单独团队数量和配对团队数量的总和
    return len(solo_teams) + len(paired)

# 输入处理
count = int(input())  # 人数
abilities = list(map(int, input().split()))  # 每个人的能力值
required_cap = int(input())  # 组成团队所需的能力值

# 输出可以组成的团队数量
print(calculate_teams(count, abilities, required_cap))
  • 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

java解法

  • 解题思路
  • 这段代码旨在计算满足条件的最大团队数。组队的规则与前面类似：

能力值大于等于所需值的成员可以独立组队。
如果两人的能力值之和大于等于所需值，他们可以组合成一个团队。
实现步骤：

对输入的能力值数组进行排序。
从数组的右端开始（最大值）找到可以独立组队的成员，统计他们的数量。
对于剩余的成员，使用双指针方法尝试配对：
如果两端之和大于等于所需值，则配对成功，计入团队数量，同时移动指针。
如果之和小于所需值，则左指针右移，尝试提高组合的总和。
返回所有团队的数量。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入人数
        int total = Integer.parseInt(scanner.nextLine());
        // 读取能力值数组并转换为整型数组
        int[] abilities = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 读取团队所需的最低能力值
        int minRequirement = Integer.parseInt(scanner.nextLine());

        // 输出最大团队数量
        System.out.println(maxTeams(total, abilities, minRequirement));
    }

    public static int maxTeams(int total, int[] abilities, int minReq) {
        // 对能力值数组进行排序（升序）
        Arrays.sort(abilities);

        int left = 0; // 左指针，指向当前最小值
        int right = total - 1; // 右指针，指向当前最大值
        int teamCount = 0; // 记录团队数量

        // 独立组队的成员（能力值大于等于所需值）
        while (right >= left && abilities[right] >= minReq) {
            right--; // 最大值已独立组队，右指针左移
            teamCount++; // 独立团队数量加1
        }

        // 两人组合的情况
        while (left < right) {
            int combined = abilities[left] + abilities[right]; // 计算当前两人能力值之和

            if (combined >= minReq) { // 如果两人之和大于等于所需值，成功配对
                teamCount++; // 组合团队数量加1
                left++; // 左指针右移，指向下一个较大值
                right--; // 右指针左移，指向下一个较小值
            } else {
                left++; // 如果组合不成功，尝试更大的最小值
            }
        }

        // 返回最大团队数量
        return teamCount;
    }
}
  • 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
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

C++解法

  • 解题思路
  • 这段代码的任务是计算满足条件的最大团队数，规则如下：

如果某人的能力值大于等于团队最低需求 minReq，该人可以单独组成一个团队。
如果两人的能力值之和大于等于 minReq，他们可以组成一个团队。
具体步骤如下：

对输入的能力值数组进行排序，从小到大排列，以便于使用双指针方法。
从右端开始，找到能力值大于等于 minReq 的人，他们可以独立组队。
对于剩下的成员，使用双指针方法尝试配对：
如果两端之和大于等于 minReq，配对成功，计入团队数量。
如果之和小于 minReq，左指针右移以尝试提高组合的总和。
返回所有团队的数量

#include 
#include 
#include 

using namespace std;

// 计算最大团队数量的函数
int maxTeams(int total, vector<int>& abilities, int minReq) {
    // 对能力值进行升序排序
    sort(abilities.begin(), abilities.end());

    int left = 0;               // 左指针，指向能力值最小的成员
    int right = total - 1;      // 右指针，指向能力值最大的成员
    int teamCount = 0;          // 记录团队数量

    // 处理可以独立组队的成员
    while (right >= left && abilities[right] >= minReq) {
        right--;                // 将独立组队的成员移出
        teamCount++;            // 团队数量加1
    }

    // 处理两人组合的情况
    while (left < right) {
        int combined = abilities[left] + abilities[right]; // 计算两人的能力值之和

        if (combined >= minReq) {  // 如果两人的能力值之和满足条件
            teamCount++;           // 计入团队
            left++;                // 左指针右移，尝试下一个较大的值
            right--;               // 右指针左移，尝试下一个较小的值
        }
        else {
            left++;                // 如果组合失败，左指针右移以尝试更大的组合
        }
    }

    // 返回总团队数量
    return teamCount;
}

int main() {
    int total;                      // 总人数
    cin >> total;
    vector<int> abilities(total);   // 存储每个人的能力值
    for (int i = 0; i < total; i++) {
        cin >> abilities[i];
    }
    int minRequirement;             // 团队所需的最低能力值
    cin >> minRequirement;

    // 输出可以组成的最大团队数量
    cout << maxTeams(total, abilities, minRequirement) << 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
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

C解法

  • 解题思路

更新中
  • 1

JS解法

  • 解题思路

  • 这段代码的目的是计算最大团队数量，规则如下：

如果某人的能力值（skills）大于或等于团队最低需求值（threshold），该人可以单独组队。
如果两人的能力值之和大于或等于 threshold，他们可以组成一个团队。
具体步骤：

对输入的能力值数组进行排序，降序排列，使较大的值优先被处理。
遍历数组前部，统计单独组队的成员数量。
使用双指针方法处理剩余的成员：
如果两个指针对应的成员能力值之和大于或等于 threshold，他们可以配对组成团队。
如果不能配对，则移动右指针，尝试寻找更小的值进行组合

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);
  if (lines.length === 3) {
    let count = parseInt(lines[0]); // 输入的成员数量
    let skills = lines[1].split(" ").slice(0, count).map(Number); // 输入的每个成员的能力值数组
    let threshold = parseInt(lines[2]); // 组队所需的最低能力值

    // 计算并输出最大团队数量
    console.log(calculateTeams(count, skills, threshold));

    // 清空输入记录
    lines.length = 0;
  }
});

function calculateTeams(count, skills, threshold) {
  // 对能力值数组进行降序排序
  skills.sort((x, y) => y - x);

  let index = 0; // 指针，指向当前独立组队的成员
  let pairs = 0; // 记录团队数量

  // 处理独立组队的成员
  while (index < count && skills[index] >= threshold) {
    pairs++; // 独立组队，团队数量加1
    index++; // 移动指针，处理下一个成员
  }

  let left = count - 1; // 双指针中的右指针，从数组末尾开始
  while (index < left) {
    // 检查两人能力值之和是否满足条件
    if (skills[index] + skills[left] >= threshold) {
      pairs++; // 成功配对，团队数量加1
      index++; // 左指针右移，指向下一个成员
      left--;  // 右指针左移，指向下一个成员
    } else {
      left--;  // 如果组合不成功，仅右指针左移
    }
  }

  // 返回团队总数量
  return pairs;
}
  • 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
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145185291"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！