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

2023年华为OD机考真题:木板

算法刷题1年前 (2023)更新 江南白衣
571 0 0
2023年华为OD机考真题:木板

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

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

题目:木板
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:小明有n块木板,第i(1<=i<=n)块木板的长度为ai。
小明买了一块长度为m的木料,这块木料可以切割成任意块,拼接到已有的木板上,用来加长木板。
小明想让最短的木板尽量长。
请问小明加长木板后,最短木板的长度最大可以为多少?
输入描述:
输入的第一行包含两个正整数,n(11n1103),m(11m1106)——n表示木板数,m表示木料长度。
输入的第二行包含n个正整数,a1,a2,,,,,an (1<=ai<=106)。
输出描述:
输出的唯一一行包含一个正整数,表示加长木板后,最短木板的长度最大可以为多少?
示例1
输入:
5 3
4 5 3 5 5
输出:
5
说明:
给第1块木板长度增加1,给第3块木板长度增加2后,这5块木板长度变为[5,5,5,5,5],最短的木板的长度最大为5。
示例2
输入:
5 2
4 5 3 5 5
输出:
4
说明:
给第3块木板长度增加1后,这5块木板长度变为[4,5,4,5,5],剩余木料的长度为1。
此时剩余木料无论给哪块木板加长,最短木料的长度都为4。
解题思路:
对其进行升序排序:34555
如例1∶有5根木材45355
1、对所有木材进行遍历,当遍历到第二根的时候,发现第二根比第—根长,第—根则加—截,3+1=4,且3-1=2
2、对所有木材进行遍历,当遍历到第三根的时候,发现第三根比第二根长,第二根则加—截,4+1=5,且2-1=1
3、对所有木材进行遍历,当遍历到第二根的时候,发现第二根比第—根长,第—根则加—截,4+1=5,且1-1=0
4、最终最短的木材是5
注意:
如果此时还有多的木材,则遍历到最后,在最后一根木板上添加—截5+1 = 6
实现代码一:
package com.codernav.demo.hwod.exam;

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

/**
 * @title 木板
 * @Description 小明有n块木板,第i(1<=i<=n)块木板的长度为ai。
 * 小明买了一块长度为m的木料,这块木料可以切割成任意块,拼接到已有的木板上,用来加长木板。
 * 小明想让最短的木板尽量长。请问小明加长木板后,最短木板的长度最大可以为多少?
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main{

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0; i<n; i++){
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums);
        while (m>0){
            m--;    //木材一段一段的截
            for(int i=1; i<n; i++){
                if(nums[i] > nums[i-1]){
                    nums[i-1] ++;   //碰到比后面的短的就加一截
                    break;
                }
                if(i == n-1){
                    nums[i] ++; //所有木材一样长则在最后一根加一截
                }
            }
        }
        System.out.println(nums[0]);
    }
}
实现代码二:
package com.codernav.demo.hwod.exam;

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

/**
 * @title 木板
 * @Description 小明有n块木板,第i(1<=i<=n)块木板的长度为ai。
 * 小明买了一块长度为m的木料,这块木料可以切割成任意块,拼接到已有的木板上,用来加长木板。
 * 小明想让最短的木板尽量长。请问小明加长木板后,最短木板的长度最大可以为多少?
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //数组长度
        int arrLen = sc.nextInt();
        //物料长度
        int len = sc.nextInt();

        int[] arr = new int[arrLen];
        int i = 0;
        while (sc.hasNext() && i < arrLen) {
            arr[i++] = sc.nextInt();
        }

        Arrays.sort(arr);
        //动态计算
        dynamicCal(arr, len);
        System.out.println(arr[0]);
    }

    public static void dynamicCal(int[] arr, int len) {
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (j + 1 < arr.length && arr[j] + 1 > arr[j + 1]) {
                    continue;
                }
                arr[j]++;
                break;
            }
        }
    }


}
© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...