【2024年华为OD机试】 (A卷,100分)- 租车骑绿岛（Java JS PythonC/C++）

一、问题描述

题目描述

部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重 M。
给出部门每个人的体重，请问最多需要租用多少双人自行车。

输入描述

第一行两个数字 m、n，分别代表自行车限重，部门总人数。

第二行，n 个数字，代表每个人的体重，体重都小于等于自行车限重 m。

• 0 < m <= 200
• 0 < n <= 1000000

输出描述

最小需要的双人自行车数量。

用例

用例 1

输入:

3 4
3 2 2 1

输出:

3

说明:
无

解题思路

1. 排序：首先将所有人的体重从小到大排序。
2. 双指针：使用双指针方法，一个指针指向最轻的人，一个指针指向最重的人。
3. 配对：尝试将最轻的人和最重的人配对，如果他们的体重之和不超过自行车的限重 M，则将他们配对，否则最重的人单独占用一辆自行车。
4. 移动指针：每次配对成功后，移动两个指针，继续尝试下一对。
5. 计数：统计需要的自行车数量。

核心思路

1. 排序：首先将所有人的体重按升序排序。
2. 处理超重个体：如果某个人的体重已经大于等于 m，则他必须单独乘坐一辆车。
3. 双指针组合：对于剩余的人，使用双指针从两端向中间遍历，尝试将最小体重和最大体重的人组合在一起。
4. 分配车辆：
   • 如果两人体重之和小于等于 m，则可以共享一辆车。
   • 如果两人体重之和大于 m，则只能让较大体重的人单独乘坐一辆车。
5. 处理剩余个体：如果最后剩下一个人未分配车辆，则需要单独为他分配一辆车。

详细步骤

1. 排序：

   • 将所有人的体重按升序排序，方便后续处理。

2. 处理超重个体：

   • 检查排序后的体重数组，从最大体重开始：
     • 如果某个人的体重大于等于 m，则他必须单独乘坐一辆车。
     • 将这个人从数组中移除，并增加车辆计数 count++。
   • 重复上述步骤，直到最大体重小于 m。

3. 双指针组合：

   • 初始化两个指针：
     • i 指向最小体重（数组开头）。
     • j 指向最大体重（数组末尾）。
   • 循环遍历数组：
     • 如果 arr[i] + arr[j] <= m，则两人可以共享一辆车，增加车辆计数 count++，并移动指针 i++ 和 j--。
     • 如果 arr[i] + arr[j] > m，则较大体重的人必须单独乘坐一辆车，增加车辆计数 count++，并移动指针 j--。

4. 处理剩余个体：

   • 如果最后 i === j，说明还有一个人未分配车辆，需要单独为他分配一辆车，增加车辆计数 count++。

5. 输出结果：

   • 最终的 count 就是所需的最少车辆数。

示例

假设有以下输入：

• 体重数组：[50, 60, 70, 80, 90]
• 车辆载重限制：m = 150

步骤解析：

1. 排序：[50, 60, 70, 80, 90]（已经是升序）。
2. 处理超重个体：
   • 最大体重 90 < 150，无需处理。
3. 双指针组合：
   • i = 0（50），j = 4（90）：
     • 50 + 90 = 140 <= 150，可以共享一辆车，count++，移动指针 i++ 和 j--。
   • i = 1（60），j = 3（80）：
     • 60 + 80 = 140 <= 150，可以共享一辆车，count++，移动指针 i++ 和 j--。
   • i = 2（70），j = 2（70）：
     • i === j，说明还有一个人未分配车辆，需要单独为他分配一辆车，count++。
4. 输出结果：
   • 最少需要 3 辆车。

总结

• 时间复杂度：排序的时间复杂度为 O(n log n)，双指针遍历的时间复杂度为 O(n)，总时间复杂度为 O(n log n)。
• 空间复杂度：排序需要 O(n) 的额外空间（如果使用原地排序则为 O(1)）。
• 核心思想：通过排序和双指针，尽可能组合出两人组，减少车辆使用。

如果有其他问题，欢迎随时提问！

二、JavaScript算法源码

以下是带有 详细中文注释 和 逻辑讲解 的 JavaScript 代码：

---

代码实现

/* 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);// 当输入行数为 2 时，表示输入完成if (lines.length === 2) {// 解析输入const [m, n] = lines[0].split(" ").map(Number); // 车辆载重限制 m，人数 nconst arr = lines[1].split(" ").map(Number); // 每个人的体重数组// 调用算法并输出结果console.log(getResult(arr, m, n));// 清空输入缓存lines.length = 0;}
});/*** 计算最少需要的车辆数* @param {number[]} arr 每个人的体重数组* @param {number} m 车辆载重限制* @param {number} n 人数* @returns {number} 最少需要的车辆数*/
function getResult(arr, m, n) {// 将体重数组按升序排序arr.sort((a, b) => a - b);let count = 0; // 车辆计数// 双指针初始化let i = 0; // 指向最小体重let j = arr.length - 1; // 指向最大体重// 双指针遍历while (i < j) {// 如果最小体重和最大体重的和小于等于 m，则可以共享一辆车if (arr[i] + arr[j] <= m) {i++; // 移动最小体重指针}j--; // 移动最大体重指针count++; // 无论是否共享，都需要一辆车}// 如果最后剩下一个人未分配车辆，则需要单独为他分配一辆车if (i === j) count++;return count;
}

---

代码逻辑讲解

1. 输入处理

• 使用 readline 模块从控制台读取输入。
• 第一行输入为车辆载重限制 m 和人数 n。
• 第二行输入为每个人的体重数组 arr。

2. 排序

• 将体重数组 arr 按升序排序，方便后续双指针操作。
• 排序后，最小体重在数组开头，最大体重在数组末尾。

3. 双指针逻辑

• 初始化两个指针：
  • i 指向最小体重（数组开头）。
  • j 指向最大体重（数组末尾）。
• 循环遍历数组：
  • 如果 arr[i] + arr[j] <= m，说明两人可以共享一辆车：
    • 移动最小体重指针 i++。
    • 移动最大体重指针 j--。
    • 增加车辆计数 count++。
  • 如果 arr[i] + arr[j] > m，说明两人无法共享一辆车：
    • 只能让较大体重的人单独乘坐一辆车。
    • 移动最大体重指针 j--。
    • 增加车辆计数 count++。

4. 处理剩余个体

• 如果最后 i === j，说明还有一个人未分配车辆：
  • 需要单独为他分配一辆车。
  • 增加车辆计数 count++。

5. 返回结果

• 最终的 count 就是所需的最少车辆数。

---

示例分析

输入

150 5
50 60 70 80 90

步骤解析

1. 排序：
   • 体重数组排序后为 [50, 60, 70, 80, 90]。
2. 双指针遍历：
   • i = 0（50），j = 4（90）：
     • 50 + 90 = 140 <= 150，可以共享一辆车。
     • 移动指针 i++ 和 j--。
     • 车辆计数 count++（count = 1）。
   • i = 1（60），j = 3（80）：
     • 60 + 80 = 140 <= 150，可以共享一辆车。
     • 移动指针 i++ 和 j--。
     • 车辆计数 count++（count = 2）。
   • i = 2（70），j = 2（70）：
     • i === j，说明还有一个人未分配车辆。
     • 需要单独为他分配一辆车。
     • 车辆计数 count++（count = 3）。
3. 输出结果：
   • 最少需要 3 辆车。

---

总结

• 时间复杂度：排序的时间复杂度为 O(n log n)，双指针遍历的时间复杂度为 O(n)，总时间复杂度为 O(n log n)。
• 空间复杂度：排序需要 O(n) 的额外空间（如果使用原地排序则为 O(1)）。
• 核心思想：通过排序和双指针，尽可能组合出两人组，减少车辆使用。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是带有 详细中文注释 和 逻辑讲解 的 Java 代码：

---

代码实现

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {// 创建 Scanner 对象，用于读取输入Scanner sc = new Scanner(System.in);// 读取车辆载重限制 m 和人数 nint m = sc.nextInt();int n = sc.nextInt();// 读取每个人的体重，并存储到数组 arr 中int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}// 调用算法并输出结果System.out.println(getResult(arr, m));}/*** 计算最少需要的车辆数* @param arr 每个人的体重数组* @param m 车辆载重限制* @return 最少需要的车辆数*/public static int getResult(int[] arr, int m) {// 将体重数组按升序排序Arrays.sort(arr);int count = 0; // 车辆计数// 双指针初始化int i = 0; // 指向最小体重int j = arr.length - 1; // 指向最大体重// 双指针遍历while (i < j) {// 如果最小体重和最大体重的和小于等于 m，则可以共享一辆车if (arr[i] + arr[j] <= m) {i++; // 移动最小体重指针}j--; // 移动最大体重指针count++; // 无论是否共享，都需要一辆车}// 如果最后剩下一个人未分配车辆，则需要单独为他分配一辆车if (i == j) count++;return count;}
}

---

代码逻辑讲解

1. 输入处理

• 使用 Scanner 从控制台读取输入。
• 第一行输入为车辆载重限制 m 和人数 n。
• 第二行输入为每个人的体重数组 arr。

2. 排序

• 使用 Arrays.sort() 将体重数组 arr 按升序排序，方便后续双指针操作。
• 排序后，最小体重在数组开头，最大体重在数组末尾。

3. 双指针逻辑

• 初始化两个指针：
  • i 指向最小体重（数组开头）。
  • j 指向最大体重（数组末尾）。
• 循环遍历数组：
  • 如果 arr[i] + arr[j] <= m，说明两人可以共享一辆车：
    • 移动最小体重指针 i++。
    • 移动最大体重指针 j--。
    • 增加车辆计数 count++。
  • 如果 arr[i] + arr[j] > m，说明两人无法共享一辆车：
    • 只能让较大体重的人单独乘坐一辆车。
    • 移动最大体重指针 j--。
    • 增加车辆计数 count++。

4. 处理剩余个体

• 如果最后 i == j，说明还有一个人未分配车辆：
  • 需要单独为他分配一辆车。
  • 增加车辆计数 count++。

5. 返回结果

• 最终的 count 就是所需的最少车辆数。

---

示例分析

输入

150 5
50 60 70 80 90

步骤解析

1. 排序：
   • 体重数组排序后为 [50, 60, 70, 80, 90]。
2. 双指针遍历：
   • i = 0（50），j = 4（90）：
     • 50 + 90 = 140 <= 150，可以共享一辆车。
     • 移动指针 i++ 和 j--。
     • 车辆计数 count++（count = 1）。
   • i = 1（60），j = 3（80）：
     • 60 + 80 = 140 <= 150，可以共享一辆车。
     • 移动指针 i++ 和 j--。
     • 车辆计数 count++（count = 2）。
   • i = 2（70），j = 2（70）：
     • i == j，说明还有一个人未分配车辆。
     • 需要单独为他分配一辆车。
     • 车辆计数 count++（count = 3）。
3. 输出结果：
   • 最少需要 3 辆车。

---

总结

• 时间复杂度：排序的时间复杂度为 O(n log n)，双指针遍历的时间复杂度为 O(n)，总时间复杂度为 O(n log n)。
• 空间复杂度：排序需要 O(n) 的额外空间（如果使用原地排序则为 O(1)）。
• 核心思想：通过排序和双指针，尽可能组合出两人组，减少车辆使用。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是带有 详细中文注释 和 逻辑讲解 的 Python 代码：

---

代码实现

# 输入获取
m, n = map(int, input().split())  # 读取车辆载重限制 m 和人数 n
arr = list(map(int, input().split()))  # 读取每个人的体重，并存储到列表 arr 中# 算法入口
def getResult(arr, m, n):arr.sort()  # 将体重列表按升序排序count = 0  # 车辆计数i = 0  # 指向最小体重j = n - 1  # 指向最大体重# 双指针遍历while i < j:# 如果最小体重和最大体重的和小于等于 m，则可以共享一辆车if arr[i] + arr[j] <= m:i += 1  # 移动最小体重指针j -= 1  # 移动最大体重指针count += 1  # 无论是否共享，都需要一辆车# 如果最后剩下一个人未分配车辆，则需要单独为他分配一辆车if i == j:count += 1return count  # 返回最少需要的车辆数# 算法调用
print(getResult(arr, m, n))

---

代码逻辑讲解

1. 输入处理

• 使用 input().split() 从控制台读取输入。
• 第一行输入为车辆载重限制 m 和人数 n。
• 第二行输入为每个人的体重列表 arr。

2. 排序

• 使用 arr.sort() 将体重列表 arr 按升序排序，方便后续双指针操作。
• 排序后，最小体重在列表开头，最大体重在列表末尾。

3. 双指针逻辑

• 初始化两个指针：
  • i 指向最小体重（列表开头）。
  • j 指向最大体重（列表末尾）。
• 循环遍历列表：
  • 如果 arr[i] + arr[j] <= m，说明两人可以共享一辆车：
    • 移动最小体重指针 i += 1。
    • 移动最大体重指针 j -= 1。
    • 增加车辆计数 count += 1。
  • 如果 arr[i] + arr[j] > m，说明两人无法共享一辆车：
    • 只能让较大体重的人单独乘坐一辆车。
    • 移动最大体重指针 j -= 1。
    • 增加车辆计数 count += 1。

4. 处理剩余个体

• 如果最后 i == j，说明还有一个人未分配车辆：
  • 需要单独为他分配一辆车。
  • 增加车辆计数 count += 1。

5. 返回结果

• 最终的 count 就是所需的最少车辆数。

---

示例分析

输入

150 5
50 60 70 80 90

步骤解析

1. 排序：
   • 体重列表排序后为 [50, 60, 70, 80, 90]。
2. 双指针遍历：
   • i = 0（50），j = 4（90）：
     • 50 + 90 = 140 <= 150，可以共享一辆车。
     • 移动指针 i += 1 和 j -= 1。
     • 车辆计数 count += 1（count = 1）。
   • i = 1（60），j = 3（80）：
     • 60 + 80 = 140 <= 150，可以共享一辆车。
     • 移动指针 i += 1 和 j -= 1。
     • 车辆计数 count += 1（count = 2）。
   • i = 2（70），j = 2（70）：
     • i == j，说明还有一个人未分配车辆。
     • 需要单独为他分配一辆车。
     • 车辆计数 count += 1（count = 3）。
3. 输出结果：
   • 最少需要 3 辆车。

---

总结

• 时间复杂度：排序的时间复杂度为 O(n log n)，双指针遍历的时间复杂度为 O(n)，总时间复杂度为 O(n log n)。
• 空间复杂度：排序需要 O(n) 的额外空间（如果使用原地排序则为 O(1)）。
• 核心思想：通过排序和双指针，尽可能组合出两人组，减少车辆使用。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是 C++ 实现 的代码，带有 详细中文注释 和 逻辑讲解：

---

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm> // 用于 sort 函数
using namespace std;// 算法入口
int getResult(vector<int>& arr, int m, int n) {sort(arr.begin(), arr.end()); // 将体重列表按升序排序int count = 0; // 车辆计数int i = 0; // 指向最小体重int j = n - 1; // 指向最大体重// 双指针遍历while (i < j) {// 如果最小体重和最大体重的和小于等于 m，则可以共享一辆车if (arr[i] + arr[j] <= m) {i++; // 移动最小体重指针}j--; // 移动最大体重指针count++; // 无论是否共享，都需要一辆车}// 如果最后剩下一个人未分配车辆，则需要单独为他分配一辆车if (i == j) {count++;}return count; // 返回最少需要的车辆数
}int main() {int m, n;cin >> m >> n; // 读取车辆载重限制 m 和人数 nvector<int> arr(n); // 定义存储体重的数组for (int i = 0; i < n; i++) {cin >> arr[i]; // 读取每个人的体重}// 调用算法并输出结果cout << getResult(arr, m, n) << endl;return 0;
}

---

代码逻辑讲解

1. 输入处理

• 使用 cin 从控制台读取输入。
• 第一行输入为车辆载重限制 m 和人数 n。
• 第二行输入为每个人的体重，存储到 vector<int> arr 中。

2. 排序

• 使用 sort(arr.begin(), arr.end()) 将体重列表 arr 按升序排序。
• 排序后，最小体重在列表开头，最大体重在列表末尾。

3. 双指针逻辑

• 初始化两个指针：
  • i 指向最小体重（列表开头）。
  • j 指向最大体重（列表末尾）。
• 循环遍历列表：
  • 如果 arr[i] + arr[j] <= m，说明两人可以共享一辆车：
    • 移动最小体重指针 i++。
    • 移动最大体重指针 j--。
    • 增加车辆计数 count++。
  • 如果 arr[i] + arr[j] > m，说明两人无法共享一辆车：
    • 只能让较大体重的人单独乘坐一辆车。
    • 移动最大体重指针 j--。
    • 增加车辆计数 count++。

4. 处理剩余个体

• 如果最后 i == j，说明还有一个人未分配车辆：
  • 需要单独为他分配一辆车。
  • 增加车辆计数 count++。

5. 返回结果

• 最终的 count 就是所需的最少车辆数。

---

示例分析

输入

150 5
50 60 70 80 90

步骤解析

1. 排序：
   • 体重列表排序后为 [50, 60, 70, 80, 90]。
2. 双指针遍历：
   • i = 0（50），j = 4（90）：
     • 50 + 90 = 140 <= 150，可以共享一辆车。
     • 移动指针 i++ 和 j--。
     • 车辆计数 count++（count = 1）。
   • i = 1（60），j = 3（80）：
     • 60 + 80 = 140 <= 150，可以共享一辆车。
     • 移动指针 i++ 和 j--。
     • 车辆计数 count++（count = 2）。
   • i = 2（70），j = 2（70）：
     • i == j，说明还有一个人未分配车辆。
     • 需要单独为他分配一辆车。
     • 车辆计数 count++（count = 3）。
3. 输出结果：
   • 最少需要 3 辆车。

---

总结

• 时间复杂度：排序的时间复杂度为 O(n log n)，双指针遍历的时间复杂度为 O(n)，总时间复杂度为 O(n log n)。
• 空间复杂度：排序需要 O(n) 的额外空间（如果使用原地排序则为 O(1)）。
• 核心思想：通过排序和双指针，尽可能组合出两人组，减少车辆使用。

如果有其他问题，欢迎随时提问！