部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重M。
给出部门每个人的体重，请问最多需要租用多少双人自行车
第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。0输出描述
用例
用例一：
输入：
3 4
3 2 2 1
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
3
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">具体步骤：
排序：
首先，对所有人的体重进行排序。这样可以方便地用双指针策略来判断是否可以将两个人放在同一辆自行车上。
双指针策略：
初始化两个指针，一个指向体重最轻的人（left），另一个指向体重最重的人（right）。
尝试将最轻和最重的两个人一起分配到一辆自行车。如果这两个人的体重之和不超过 max_weight，则可以将这两个人分配到同一辆车上。此时，left 指针向右移动（代表最轻的人已经分配完），right 指针向左移动（代表最重的人也分配完）。
如果这两个人的体重之和超过了 max_weight，则只能将最重的人单独分配到一辆车上，right 指针向左移动。
重复这个过程，直到所有人都分配上自行车。
结束条件：
当 left 指针超过 right 指针时，说明所有人都已经被分配完自行车。
时间复杂度：
排序操作的时间复杂度是 O(n log n)，而双指针扫描的时间复杂度是 O(n)。因此，总的时间复杂度是 O(n log n)。
def calculate_bikes(weights, max_weight, total_people):
# 先对所有人的体重进行排序
weights.sort()
# 初始化指针
left, right = 0, total_people - 1
bikes = 0 # 记录分配的自行车数
# 使用双指针策略进行分配
for _ in range(total_people):
# 如果left指针还没超过right指针，说明还有人未分配
if left <= right:
# 如果当前最轻的人和最重的人的体重和小于等于max_weight，放在同一辆车
if weights[left] + weights[right] <= max_weight:
left += 1 # 最轻的人已经分配好，left指针向右移动
# 不论是否配对成功，最重的人一定需要一辆车
right -= 1 # 最重的人已经分配好，right指针向左移动
bikes += 1 # 增加分配的自行车数量
else:
break # 如果所有人都已经分配完，结束循环
return bikes
# 输入：第一行是最大载重和总人数，第二行是每个人的体重
m, n = map(int, input().split())
weights = list(map(int, input().split()))
# 调用函数并输出结果
print(calculate_bikes(weights, m, n))
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">步骤：
排序：
首先，对所有人的体重进行排序。排序后，我们可以尝试将体重最轻的人和最重的人放在同一辆车上。
双指针策略：
初始化两个指针，i 指向体重最轻的人（从左边开始），j 指向体重最重的人（从右边开始）。
每次尝试将 arr[i]（最轻的）和 arr[j]（最重的）放在同一辆车上。如果这两个人的体重和小于等于 m，则可以将他们放在同一辆车上，此时将 i 指针向右移动，j 指针向左移动；否则，将最重的人单独分配到一辆车上，j 指针向左移动。
每次分配一辆车时，增加 groups 计数器。
结束条件：
当 i 指针超过 j 指针时，说明所有人已经被分配到车上。
时间复杂度：
排序的时间复杂度是 O(n log n)，双指针扫描的时间复杂度是 O(n)。因此，总的时间复杂度是 O(n log n)。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取最大承载重量和总人数
int m = sc.nextInt();
int n = sc.nextInt();
// 读取每个人的体重
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 调用计算函数并输出结果
System.out.println(calculate(arr, m));
}
// 计算需要的最小车数
public static int calculate(int[] arr, int m) {
// 对体重数组进行排序
Arrays.sort(arr);
// 初始化车数计数器
int groups = 0;
// 双指针：i指向最轻的，j指向最重的
for (int i = 0, j = arr.length - 1; i <= j; j--) {
// 如果最轻和最重的两个人可以共享一辆车
if (arr[i] + arr[j] <= m) {
i++; // 最轻的人上车，i指针右移
}
// 无论是否配对，都需要为当前最重的人分配一辆车
groups++; // 增加车数
}
// 返回所需的最小车数
return groups;
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">解决思路：
排序：
首先，对所有人的体重进行排序。这样可以利用双指针方法，高效地将最轻和最重的人配对，尽量减少车的数量。
双指针策略：
使用两个指针，l 指向体重最轻的人，r 指向体重最重的人。
每次检查 nums[l] + nums[r] 是否小于或等于 lim，即是否可以将 l 和 r 指向的两个人放在同一辆车上：
如果可以，将这两个人放在同一辆车上，并且分别移动两个指针（l++，r–）。
如果不可以，则只能将最重的人单独分配一辆车，移动 r–。
继续执行这个过程，直到所有人都分配到车上。
结束条件：
当 l 和 r 重合时，说明只剩一个人，该人单独一辆车。
最终返回：
返回分配的车数。
时间复杂度：
排序的时间复杂度是 O(n log n)，双指针扫描的时间复杂度是 O(n)。因此，总的时间复杂度是 O(n log n)。
#include 首先，对所有人的体重进行排序。排序后，我们可以利用双指针方法，高效地将最轻和最重的人配对，尽量减少车的数量。
双指针策略：
使用两个指针，l 指向体重最轻的人，r 指向体重最重的人。
每次检查 nums[l] + nums[r] 是否小于或等于 lim，即是否可以将 l 和 r 指向的两个人放在同一辆车上：
如果可以，将这两个人放在同一辆车上，并且分别移动两个指针（l++，r–）。
如果不可以，则只能将最重的人单独分配一辆车，移动 r–。
继续执行这个过程，直到所有人都分配到车上。
结束条件：
当 l 和 r 重合时，说明只剩一个人，该人单独一辆车。
最终返回：
返回分配的车数。
时间复杂度：
排序的时间复杂度是 O(n log n)，双指针扫描的时间复杂度是 O(n)。因此，总的时间复杂度是 O(n log n)。
#include 更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：