【2024最新华为OD-D卷试题汇总】最多可以派出多少支团队(100分) - 三语言AC题解(Python/Java/Cpp)

5
3 1 5 7 9
8

3

3`和`5`组成一队，`1`和`7`组成一队，`9`自己一个队，故输出`3

# 题目：【贪心】2023C-最多可以派出多少支团队
# 分值：100
# 算法：贪心/双指针
# 代码看不懂的地方，请直接在群上提问
# 练习平台：https://oj.algomooc.com/
# 题目汇总：https://www.algomooc.com/3159.html


# 数组长度
n = int(input())
# 数组
nums = list(map(int, input().split()))
# 最小能力值要求
m = int(input())

# 对nums进行排序，方便使用头尾相向双指针
nums.sort()
# 如果nums的最小值已经大于m，则每一个人都单独组队，直接输出n
if nums[0] >= m:
    print(n)
# 否则，实现贪心+双指针算法
else:
    # 设置头尾双指针
    left, right = 0, n-1
    # 初始化答案变量
    ans = 0
    # 循环遍历，退出循环的条件为left和right指向同一个元素
    while left < right:
        # 如果nums[right]本身已经大于等于m，则nums[right]单独组队
        # right递减，ans更新
        if nums[right] >= m:
            right -= 1
            ans += 1
        # 如果当前剩余数字中的最大值和最小值相加大于等于m
        # 则说明nums[right]带得动nums[left]
        # 贪心地令它们进行组队，两个指针向中间移动，ans更新
        elif nums[right] + nums[left] >= m:
            left += 1
            right -= 1
            ans += 1
        # 如果当前剩余数字中的最大值和最小值相加小于m
        # 则说明即使是能力值最大的nums[right]也带不动nums[left]
        # nums[left]不应该去组队，left递增以找到一个更大的能力值
        else:
            left += 1
    # 退出循环时，存在left >= right
    # 可能出现left = right的情况
    # 但由于所有可以单独组队的right都已经被排除
    # 且最终right不可能降为0
    # （因为nums[0] >= m的情况已经在前面的if判断过了）
    # 故此时nums[left] = nums[right]不能单独组队
    # 直接输出ans即为答案
    print(ans)

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        int m = scanner.nextInt();
        
        Arrays.sort(nums);
        
        if (nums[0] >= m) {
            System.out.println(n);
        } else {
            int left = 0, right = n - 1;
            int ans = 0;
            
            while (left < right) {
                if (nums[right] >= m) {
                    right--;
                    ans++;
                } else if (nums[right] + nums[left] >= m) {
                    left++;
                    right--;
                    ans++;
                } else {
                    left++;
                }
            }
            
            System.out.println(ans);
        }
    }
}

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
    }
    
    int m;
    std::cin >> m;

    std::sort(nums.begin(), nums.end());

    if (nums[0] >= m) {
        std::cout << n << std::endl;
    } else {
        int left = 0, right = n - 1;
        int ans = 0;

        while (left < right) {
            if (nums[right] >= m) {
                right--;
                ans++;
            } else if (nums[right] + nums[left] >= m) {
                left++;
                right--;
                ans++;
            } else {
                left++;
            }
        }

        std::cout << ans << std::endl;
    }

    return 0;
}