求最多可以派出多少只团队 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

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

请计算出最多可以派出多少支符合要求的团队

输入描述

5 3 1 5 7 9 8 第一行代表总人数，范围[1,500000]

第二行数组代表每个人的能力，每个元素的取值范围为[1,500000],数组的大小范围[1,500000]

第三行数值为团队要求的最低能力值，范围[1,500000]

输出描述

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

示例1

输入：
5
3 1 5 7 9
8

输出：
3

说明：
3，5组成一队，1，7组成一队，9自己一个队，故而输出3

题解

这道题的解法思路是使用贪心算法。首先，将每个人的能力值进行排序，然后使用双指针分别指向数组的开头和结尾。接着，根据题目要求的团队最低能力值，从两端向中间逼近，不断组成团队，直到两指针相遇。

具体实现步骤如下：

将每个人的能力值数组进行排序。

初始化团队数量为0。

使用两个指针l和r分别指向数组的开头和结尾。

不断判断当前指向的两个人的能力值之和是否大于等于团队要求的最低能力值，如果是，则这两个人可以组成一个团队，团队数量加1，同时将指针向中间移动；如果不是，则判断能力较小的那个人是否能够和其他人组成团队，不能的话就抛弃该人，指针向中间移动。

重复步骤4，直到两个指针相遇。

最终，团队数量即为所求结果。

Java

import java.util.Arrays;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {

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

        int n = scanner.nextInt();

        // 每个人的能力
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = scanner.nextInt();
        }

        // 团队要求的最低能力值
        int bound = scanner.nextInt();

        Arrays.sort(p);

        int teams = 0;

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

2024华为OD机试真题题解文章被收录于专栏

华为OD机考（C卷、D卷）算法题库（绝对都是原题），帮助你上岸华为（已经不少小伙伴成功上岸）。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题，随时解答。从 2024年4月24开始，考的都是华为OD统一考试（D卷），据已经参加D卷考试的同学反馈D卷和C卷是一样的，如果发现新题会及时更新。

全部评论

推荐最新楼层

FerryMan_liu

Java

配对问题，可以使用匈牙利算法

送花回复

发布于 04-24 17:43 浙江

FerryMan_liu

Java

public class Z75 { public static int solution(int[] arr, int target) { int count = 0; int[] result = new int[arr.length]; Arrays.fill(result, -1); for (int i = 0; i < arr.length; i++) { boolean[] isUsed = new boolean[arr.length]; if (canSelected(arr, i, result, isUsed, target)) { count++; } } for (int i= 0; i < arr.length; i++) { if (arr[i] >= target && result[i] == -1) { count++; } } return count; } public static boolean canSelected(int[] arr, int i, int[] result, boolean[] isUsed, int target) { for (int j = 0; j < arr.length; j++) { if (i == j) { continue; } if (isUsed[j]) { continue; } if (arr[i] + arr[j] < target) { continue; } if (result[j] == -1) { result[i] = j; result[j] = i; return true; } int nextI = result[j]; if (nextI == i) { return false; } isUsed[j] = true; isUsed[i] = true; if (canSelected(arr, nextI, result, isUsed, target)) { result[i] = j; result[j] = i; return true; } } return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } int m = sc.nextInt(); System.out.println((solution(arr, m))); } }

送花回复

发布于 04-24 17:44 浙江