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

发布于:2024-11-29 ⋅ 阅读:(30) ⋅ 点赞:(0)

一、题目描述

部门组织绿岛骑行团建活动。租用公共双人自行车,每辆自行车最多坐两人,做最大载重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方法中,首先对体重数组进行排序。
    • 使用两个指针lightestheaviest分别指向体重数组的最轻和最重的人。
    • 通过一个循环,尝试将最轻和最重的人配对在同一辆自行车上(如果他们的体重之和不超过最大载重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 = 0heaviest = 3bikes = 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辆自行车。
  • 这种方法的关键在于通过排序和双指针技术来优化配对过程,从而尽量减少所需的双人自行车数量。