2023年华为OD机考真题：租车骑绿道

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：租车骑绿道
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
部门组织绿道骑行团建活动。租用公共双人自行车骑行，每辆自行车最多坐两人、做大载重M。
给出部门每个人的体重，请问最多需要租用多少双人自行车。
输入描述：
第一行两个数字m、n，自行车限重m，代表部门总人数n。
第二行，n个数字，代表每个人的体重。体重都小于等于自行车限重m。
0 < m <= 200
0 < n <= 1000000
输出描述：
最小需要的双人自行车数量。
示例1
输入：
3 4
3 2 2 1
输出：
3
解题思路：
对部门人员按照体重进行降序排序。
对人员进行遍历。
如例1：
排序后为 3 2 2 1
1、3 等于承重3，则单独一辆 count = 1；
2、2 小于3，继续向前找，2+2=4不符合，继续向前找，2+1=3等于3，符合，1已经用过了需要置为0，count+1 = 2；
3,、2 小于3，向前找，只剩刚才处理过的0，遍历结束。结果count+1=3；

代码实现一：

package com.codernav.demo.hwod.exam;

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

/**
 * @title 租车骑绿道
 * @Description 部门组织绿道骑行团建活动。租用公共双人自行车骑行，每辆自行车最多坐两人、做大载重M。
 * 给出部门每个人的体重，请问最多需要租用多少双人自行车。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] weight = new int[n];
        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
        }
        Arrays.sort(weight);    //对体重进行排序，方便安排
        int res = 0;
        for (int i = weight.length - 1; i >= 0; i--) {
            if (weight[i] == 0) {     //等于0则代表已经有车了
                continue;
            }
            if (weight[i] == m) {     //一人一辆车
                res++;
                continue;
            }
            for (int j = i - 1; j >= 0; j--) {
                if (weight[j] != 0 && weight[i] + weight[j] <= m) {   //因为已经排过序，遇到合适的就上车
                    weight[j] = 0;
                    break;
                }
            }
            res++;
        }
        System.out.println(res);
    }

}

代码实现二：Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * @title 租车骑绿道
 * @Description 部门组织绿道骑行团建活动。租用公共双人自行车骑行，每辆自行车最多坐两人、做大载重M。
 * 给出部门每个人的体重，请问最多需要租用多少双人自行车。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static void main(String[] args) {
        //处理输入
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        ArrayList<Integer> weights = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            weights.add(a);
            //System.out.println(s);
        }
        Collections.sort(weights);
        //第二步，左右指针向中间移动
        int left = 0;
        int right = weights.size() - 1;
        //结果
        int min_bikes = 0;
        //当前重量
        int temp_weight = weights.get(right) + weights.get(left);
        // 题目中有两个隐含的条件
        // 1: 一辆车最多骑两个人
        // 2：人的重量不可能大于车的载重
        while (left < right) {
            if (temp_weight > m) {
                right--;
                min_bikes += 1;
                temp_weight = weights.get(right) + weights.get(left);
            } else {
                right--;
                left++;
                min_bikes += 1;
                temp_weight = weights.get(right) + weights.get(left);
            }
        }
        if (left == right) {
            min_bikes++;
        }
        System.out.println(min_bikes);
    }
}