问题描述

给定一个数组，代表每个人的能力值。比赛要求团队的最低能力值为 $N$，每个团队可以由 $1$ 人或 $2$ 人组成，每个人只能参加一个团队。要求计算最多可以派出的符合要求的团队数量。

思路

该问题的核心思路是通过贪心策略，优先将能力值较高的人单独组成团队，然后再尽可能将剩余的人配对成两人团队。首先对所有人的能力值进行排序，然后通过双指针的方式，从数组两端开始尝试配对，如果两个人的能力值之和大于等于最低要求，则组成一个团队；如果不能配对，则将能力值较高的人单独作为一个团队。通过这种策略，可以最大化符合要求的团队数量。

具体策略如下：

1. 排序：将能力值数组从小到大排序，便于后续处理。

2. 统计单人团队：首先统计能力值大于等于 $N$ 的人员数量，这些人可以单独组成团队。

3. 双指针配对：对于剩下的能力值小于 $N$ 的人员，使用双指针从两端向中间遍历，尝试将能力值最小和最大的人员配对，若两人的能力值之和不小于 $N$，则组成一个团队。

4. 移动指针：

   • 如果配对成功：团队数量加 1，左指针右移，右指针左移。
   • 如果配对失败：左指针右移，尝试下一个能力值较大的人员与右指针对应的人配对。

cpp

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

int main() {
    int n; // 总人数
    std::cin >> n;
    std::vector<int> abilities(n); // 每个人的能力值

    for (int i = 0; i < n; ++i) {
        std::cin >> abilities[i];
    }

    int N; // 团队要求的最低能力值
    std::cin >> N;

    // 将能力值从小到大排序
    std::sort(abilities.begin(), abilities.end());

    int team_count = 0; // 符合要求的团队数量

    // 统计可以单独组成团队的人数
    int single_teams = 0;
    int left = 0; // 左指针，指向能力值小于 N 的第一个人
    int right = n - 1; // 右指针，初始为数组末尾

    while (right >= 0 && abilities[right] >= N) {
        single_teams++; // 能力值大于等于 N，可以单独组队
        right--; // 右指针左移
    }

    // 对于剩余的人，尝试两人配对
    while (left < right) {
        if (abilities[left] + abilities[right] >= N) {
            team_count++; // 配对成功，团队数量加 1
            left++;       // 左指针右移
            right--;      // 右指针左移
        } else {
            left++;       // 配对失败，左指针右移
        }
    }

    team_count += single_teams; // 总团队数量等于配对成功的团队数加上单人团队数

    std::cout << team_count << std::endl; // 输出最多可以派出的团队数量

    return 0;
}

python

# 读取输入
n = int(input())  # 总人数
abilities = list(map(int, input().split()))  # 每个人的能力值
N = int(input())  # 团队要求的最低能力值

abilities.sort()  # 将能力值从小到大排序

team_count = 0    # 符合要求的团队数量

# 统计可以单独组成团队的人数
single_teams = 0
left = 0          # 左指针，指向能力值小于 N 的第一个人
right = n - 1     # 右指针，初始为数组末尾

while right >= 0 and abilities[right] >= N:
    single_teams += 1   # 能力值大于等于 N，可以单独组队
    right -= 1          # 右指针左移

# 对于剩余的人，尝试两人配对
while left < right:
    if abilities[left] + abilities[right] >= N:
        team_count += 1  # 配对成功，团队数量加 1
        left += 1        # 左指针右移
        right -= 1       # 右指针左移
    else:
        left += 1        # 配对失败，左指针右移

team_count += single_teams  # 总团队数量等于配对成功的团队数加上单人团队数

print(team_count)           # 输出最多可以派出的团队数量

java

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

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

        int n = sc.nextInt();           // 总人数
        int[] abilities = new int[n];   // 每个人的能力值

        for (int i = 0; i < n; i++) {
            abilities[i] = sc.nextInt();
        }

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

        Arrays.sort(abilities);         // 将能力值从小到大排序

        int team_count = 0;             // 符合要求的团队数量

        // 统计可以单独组成团队的人数
        int single_teams = 0;
        int left = 0;                   // 左指针，指向能力值小于 N 的第一个人
        int right = n - 1;              // 右指针，初始为数组末尾

        while (right >= 0 && abilities[right] >= N) {
            single_teams++;             // 能力值大于等于 N，可以单独组队
            right--;                    // 右指针左移
        }

        // 对于剩余的人，尝试两人配对
        while (left < right) {
            if (abilities[left] + abilities[right] >= N) {
                team_count++;           // 配对成功，团队数量加 1
                left++;                 // 左指针右移
                right--;                // 右指针左移
            } else {
                left++;                 // 配对失败，左指针右移
            }
        }

        team_count += single_teams;     // 总团队数量等于配对成功的团队数加上单人团队数

        System.out.println(team_count); // 输出最多可以派出的团队数量
    }
}

题目描述

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

输入描述

第一行代表总人数，范围 $1-500000$

第二行数组代表每个人的能力

数组大小，范围 $1-500000$

元素取值，范围 $1-500000$

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

输出描述

最多可以派出的团队数量

样例1

输入

5
3 1 5 7 9
8

输出

3

说明

$3$、$5$ 组成一队 $1$、$7$ 一队 $9$ 自己一队 输出 $3$

样例2

输入

7
3 1 5 7 9 2 6
8

输出

4

说明

$3$、$5$ 组成一队，$1$、$7$ 一队，$9$ 自己一队，$2$、$6$ 一队，输出 $4$

样例3

输入

3
1 1 9
8

输出

1

说明

$9$ 自己一队，输出 $1$