Loading...
百度&必应权4, 日IP8000. 查看详情
自助收录

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

算法刷题1年前 (2023)更新 江南白衣
416 0 0
2023年华为OD机考真题:租车骑绿道

全网最全面的华为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);
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...