返回目录

题目描述

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

输入描述

第一行代表总人数，范围1-500000
第二行数组代表每个人的能力

• 数组大小，范围1-500000
• 元素取值，范围1-500000
  第三行数值为团队要求的最低能力值，范围1-500000

输出描述

最多可以派出的团队数量

示例：

Python算法源码

def main():
    n = int(input())  # 输入人数
    capacities = list(map(int, input().split()))  # 输入每个人的能力值
    min_cap = int(input())  # 输入最小组队能力值

    print(get_result(n, capacities, min_cap))


def get_result(n, capacities, min_cap):
    # 升序排序
    capacities.sort()

    l = 0
    r = n - 1

    # 记录结果
    ans = 0

    # 单人组队
    while r >= l and capacities[r] >= min_cap:
        r -= 1
        ans += 1

    # 双人组队
    while l < r:
        total = capacities[l] + capacities[r]

        # 如果两个人的能力之和大于等于最小能力值，则组队成功
        if total >= min_cap:
            ans += 1
            l += 1
            r -= 1
        else:
            # 否则，将能力较低的人剔除，尝试下一个能力较高的人
            l += 1

    return ans


if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int getResult(int n, int capacities[], int minCap) {
    // 升序排序
    qsort(capacities, n, sizeof(int), compare);

    int l = 0;
    int r = n - 1;

    // 记录结果
    int ans = 0;

    // 单人组队
    while (r >= l && capacities[r] >= minCap) {
        ans++;
        r--;
    }

    // 双人组队
    while (l < r) {
        int total = capacities[l] + capacities[r];

        // 如果两个人的能力之和大于等于最小能力值，则组队成功
        if (total >= minCap) {
            ans++;
            l++;
            r--;
        } else {
            // 否则，将能力较低的人剔除，尝试下一个能力较高的人
            l++;
        }
    }

    return ans;
}

int main() {
    int n;
    scanf("%d", &n); // 输入人数
    int *capacities = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &capacities[i]); // 输入每个人的能力值
    }
    int minCap;
    scanf("%d", &minCap); // 输入最小组队能力值

    printf("%d\n", getResult(n, capacities, minCap));

    free(capacities);
    return 0;
}

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 n = scanner.nextInt(); // 输入人数
        int[] capacities = new int[n]; // 存储每个人的能力值
        for (int i = 0; i < n; i++) {
            capacities[i] = scanner.nextInt(); // 输入每个人的能力值
        }
        int minCap = scanner.nextInt(); // 输入最小组队能力值

        System.out.println(getResult(n, capacities, minCap));
    }

    public static int getResult(int n, int[] capacities, int minCap) {
        // 升序排序
        Arrays.sort(capacities);

        int l = 0;
        int r = n - 1;

        // 记录结果
        int ans = 0;

        // 单人组队
        while (r >= l && capacities[r] >= minCap) {
            ans++;
            r--;
        }

        // 双人组队
        while (l < r) {
            int total = capacities[l] + capacities[r];

            // 如果两个人的能力之和大于等于最小能力值，则组队成功
            if (total >= minCap) {
                ans++;
                l++;
                r--;
            } else {
                // 否则，将能力较低的人剔除，尝试下一个能力较高的人
                l++;
            }
        }

        return ans;
    }
}