华为OD机试真题---租车骑绿道

一、题目描述

部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，做最大载重M。给出部门每个人的体重，请问最多需要租用多少双人自行车。
输入描述:
第一行两个数字m、n，分别代表自行车限重，部门总人数。第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。

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

输出描述:
最小需要的双人自行车数量。
示例1
输入输出示例仅供调试，后台判题数据一般不包含示例输入

3 4
3 2 2 1

输出

3

二、解题思路

此问题可以通过贪心算法解决。核心思想是尽可能让两个人一起骑一辆车，从而减少所需的自行车总数。具体步骤如下：

• 排序：首先将所有人的体重从小到大排序。
• 双指针：使用两个指针，一个指向最轻的人（lightest），另一个指向最重的人（heaviest）。
• 匹配：尝试将最轻的人和最重的人配对。如果他们的体重之和不超过自行车的最大载重m，则他们可以共乘一辆车，同时移动两个指针；否则，只有最重的人单独乘坐一辆车，移动指向最重者的指针。
• 计数：每次成功配对或单独安排一个人后，自行车的数量增加1。
• 终止条件：当两个指针相遇或交错时，结束循环，此时的计数即为所需自行车的最小数量。

三、代码实现

import java.util.Arrays;
import java.util.Scanner;

public class BikeRental {

    /**
     * 计算最少需要租用的双人自行车数量。
     * @param m 自行车的最大载重。
     * @param weights 一个整数数组，表示每个人的实际体重。
     * @return 最少需要租用的双人自行车数量。
     */
    public static int minBikesRequired(int m, int[] weights) {
        // 对体重数组进行排序
        Arrays.sort(weights);
        // 指向最轻的人
        int lightest = 0;
        // 指向最重的人
        int heaviest = weights.length - 1;
        // 记录需要的自行车数量
        int bikes = 0;

        while (lightest <= heaviest) {
            // 当最轻和最重的人能共乘一辆车时
            if (weights[lightest] + weights[heaviest] <= m) {
                // 移动轻者指针
                lightest++;
            }
            // 无论是否共乘，重者指针都要移动
            heaviest--;
            // 每次循环自行车数量加1
            bikes++;
        }

        return bikes;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 自行车的最大载重
        int m = scanner.nextInt();
        // 人数
        int n = scanner.nextInt();
        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            // 读取每个人的体重
            weights[i] = scanner.nextInt();
        }

        int result = minBikesRequired(m, weights);
        // 输出结果
        System.out.println("最小需要的双人自行车数量:"+result);

        scanner.close();
    }
}

四、代码与运行示例解析

代码解析

1. 输入读取：

   • 程序首先通过Scanner对象从标准输入读取两个整数：自行车的最大载重m和部门总人数n。
   • 接着，读取n个整数，表示每个人的体重，并将这些体重存储在数组weights中。

2. 方法调用：

   • 调用minBikesRequired方法，传入最大载重m和体重数组weights，该方法返回所需的最少双人自行车数量。

3. 方法实现：

   • 在minBikesRequired方法中，首先对体重数组进行排序。
   • 使用两个指针lightest和heaviest分别指向体重数组的最轻和最重的人。
   • 通过一个循环，尝试将最轻和最重的人配对在同一辆自行车上（如果他们的体重之和不超过最大载重m）。
   • 在每次循环中，无论是否成功配对，都将heaviest指针向左移动（表示最重的人已经被处理），并且自行车数量bikes加一。
   • 如果最轻和最重的人能够配对，则也将lightest指针向右移动（表示最轻的人也被处理）。
   • 当lightest指针超过heaviest指针时，循环结束，此时bikes的值即为所需的最少双人自行车数量。

运行示例解析

输入：

3 4
3 2 2 1

步骤：

1. 输入读取：

   • m = 3
   • n = 4
   • weights = [3, 2, 2, 1]

2. 排序：

   • 排序后的weights = [1, 2, 2, 3]

3. 配对与计数：

   • 初始化lightest = 0，heaviest = 3，bikes = 0
   • 第一轮循环：
     • weights[lightest] + weights[heaviest] = 1 + 3 = 4（超过m，不能配对）
     • heaviest减一，变为2
     • bikes加一，变为1
   • 第二轮循环：
     • weights[lightest] + weights[heaviest] = 1 + 2 = 3（等于m，可以配对）
     • lightest加一，变为1
     • heaviest减一，变为1
     • bikes加一，变为2
   • 第三轮循环：
     • weights[lightest] + weights[heaviest] = 2 + 2 = 4（超过m，不能配对）
     • heaviest减一，变为0
     • bikes加一，变为3
     • 循环结束（因为lightest已经大于heaviest）

4. 输出结果：

   • 输出最小需要的双人自行车数量:3

五、注意事项

• 在上述示例中，虽然第三轮循环中的两个人（体重都为2）不能共乘一辆自行车，但由于我们已经为他们各自分配了一辆自行车（在第二轮和第三轮循环中），所以最终结果仍然是3辆自行车。
• 这种方法的关键在于通过排序和双指针技术来优化配对过程，从而尽量减少所需的双人自行车数量。