(C卷,100分)- 求最多可以派出多少支团队（Java & JS & Python & C）

题目描述

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

输入描述

• 第一行代表总人数，范围1-500000
• 第二行数组代表每个人的能力
  • 数组大小，范围1-500000
  • 元素取值，范围1-500000
• 第三行数值为团队要求的最低能力值，范围1-500000

输出描述

最多可以派出的团队数量

用例

题目解析

本题要求最多的组队，而组队要求是：

• 可以1人组队，也可以2人组队
• 团队的能力值之和需要大于等于最低能力minCap要求

因此，为了组更多队伍，我们应该尽量让单人组队，即：

• 需要将能力值大于等于minCap的筛选出来，单人组队

然后剩余的人，按照能力值升序排序，定义L,R指针，初始时L=0，R=k-1，k是剩余人总数

接着尝试L，R进行组队：

• 如果L，R两人的能力之和大于等于minCap，则组队成功，L++，R–
• 否则，说明L无法和任何人组队，因为R已经是当前最高能力的人，L无法和R组队，则也意味着无法和能力值比R低的人组队，因此L++

在上面过程中，计算出组队个数作为题解。

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 = Integer.parseInt(sc.nextLine());

    int[] capacities =
        Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    int minCap = Integer.parseInt(sc.nextLine());

    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) {
      r--;
      ans++;
    }

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

      // 如果两个人的能力值之和>=minCap，则组队
      if (sum >= minCap) {
        ans++;
        l++;
        r--;
      } else {
        // 否则将能力低的人剔除，换下一个能力更高的人
        l++;
      }
    }

    return ans;
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 3) {
    let n = parseInt(lines[0]);
    let capacities = lines[1].split(" ").slice(0, n).map(Number);
    let minCap = parseInt(lines[2]);

    console.log(getResult(n, capacities, minCap));

    lines.length = 0;
  }
});

function getResult(n, capacities, minCap) {
  // 升序
  capacities.sort((a, b) => a - b);

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

  // 记录题解
  let ans = 0;

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

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

    // 如果两个人的能力值之和>=minCap，则组队
    if (sum >= minCap) {
      ans++;
      l++;
      r--;
    } else {
      // 否则将能力低的人剔除，换下一个能力更高的人
      l++;
    }
  }

  return ans;
}

Python算法源码

# 输入获取
n = int(input())
capacities = list(map(int, input().split()))
minCap = int(input())


# 算法入口
def getResult():
    # 升序
    capacities.sort()

    l = 0
    r = n - 1

    # 记录题解
    ans = 0

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

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

        # 如果两个人的能力值之和>=minCap，则组队
        if total >= minCap:
            ans += 1
            l += 1
            r -= 1
        else:
            # 否则将能力低的人剔除，换下一个能力更高的人
            l += 1

    return ans


# 调用算法
print(getResult())

C算法源码

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

#define MAX(a,b) ((a) > (b) ? (a) : (b))

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

int main() {
    int n;
    scanf("%d", &n);

    int capacities[n];
    for(int i=0; i<n; i++) {
        scanf("%d", &capacities[i]);
    }

    int minCap;
    scanf("%d", &minCap);

    // 升序
    qsort(capacities, n, sizeof(int), cmp);

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

    // 记录题解
    int ans = 0;

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

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

        if(sum >= minCap) {
            // 如果两个人的能力值之和>=minCap，则组队
            ans++;
            l++;
            r--;
        } else {
            // 否则将能力低的人剔除，换下一个能力更高的人
            l++;
        }
    }

    printf("%dn", ans);

    return 0;
}