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

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为 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

题解

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

具体实现步骤如下：

1. 将每个人的能力值数组进行排序。
2. 初始化团队数量为0。
3. 使用两个指针l和r分别指向数组的开头和结尾。
4. 不断判断当前指向的两个人的能力值之和是否大于等于团队要求的最低能力值，如果是，则这两个人可以组成一个团队，团队数量加1，同时将指针向中间移动；如果不是，则判断能力较小的那个人是否能够和其他人组成团队，不能的话就抛弃该人，指针向中间移动。
5. 重复步骤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;
        int l = 0, r = n - 1;
        while (l <= r) {
            if (p[r] >= bound) {  // 一个人组成一个团队
                r--;
            } else if (l != r && p[l] + p[r] >= bound) {   // 两个人可以组成一个团队
                l++;
                r--;
            } else { // p[l] 太小，两个人也组成不了团队，则抛弃掉
                l++;
                continue;
            }

            teams++;
        }

        System.out.println(teams);
    }
}

Python

# 输入团队人数
n = int(input())

# 输入每个人的能力值
p = list(map(int, input().split()))

# 输入团队要求的最低能力值
bound = int(input())

# 对能力值进行排序
p.sort()

# 初始化团队数量
teams = 0

# 初始化左右指针
l, r = 0, n - 1

# 循环处理直到左指针大于右指针
while l <= r:
    if p[r] >= bound:
        # 一个人组成一个团队
        r -= 1
    elif l != r and p[l] + p[r] >= bound:
        # 两个人可以组成一个团队
        l += 1
        r -= 1
    else:
        # p[l] 太小，两个人也组成不了团队，则抛弃掉
        l += 1
        continue
    
    # 记录团队数量
    teams += 1

# 输出团队数量
print(teams)

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    // 每个人的能力
    vector<int> p(n);
    for(int i = 0; i < n; i++) cin >> p[i];

    // 团队要求的最低能力值
    int bound;
    cin >> bound;

    sort(p.begin(), p.end());

    int teams = 0;
    int l = 0, r = n - 1;
    while(l <= r){
        if(p[r] >= bound){  // 一个人组成一个团队
            r--;
        }else if(l != r && p[l] + p[r] >= bound){   // 两个人可以组成一个团队
            l++;
            r--;
        }else{ // p[l] 太小，两个人也组成不了团队，则抛弃掉
            l++;
            continue;
        }
        
        teams++;
    }

    cout << teams << endl;

    return 0;
}    

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏