可以派出多少支团
题目描述
用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N，每个团队可以由1人或2人组成，且1个人只能参加1个团队，请计算出最多可以派出多少支符合要求的团队?
输入描述
第一行数组代表总人数，范围[1,500000]
第二行数组代表每个人的能力，每个元素的取值范围[1,500000]，数组的大小范围[1,500000]
第三行数值为团队要求的最低能力值，范围[1,500000]
输出描述
最多可以派出的团队数量
示例
输入
代码语言：javascript复制5
3 1 5 7 9
8
输出
代码语言：javascript复制3
说明
代码语言：javascript复制3`和`5`组成一队，`1`和`7`组成一队，`9`自己一个队，故输出`3
解题思路
一道非常典型的双指针贪心题，类似于求下限版本的LC881. 救生艇
代码
Python
代码语言：javascript复制# 题目：【贪心】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)
Java
代码语言：javascript复制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);
}
}
}
C
代码语言：javascript复制#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;
}
想要实战演练的可以访问这个链接：https://oj.algomooc.com/problem.php?id=3117
