2023年华为OD机考真题：不爱施肥的小布

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

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

题目：不爱施肥的小布
知识点二分查找
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
某农场主管理了一大片果园，fields[i] 表示不同果林的面积，单位:(m^2)，现在要为所有的果林施肥且必须在 n 天之内完成，否则影响收成。小布是果林的工作人员，他每次选择一片果林进行施肥，且一片果林施肥完后当天不再进行施肥作业。假设施肥机的能效为k，单位:(m^2/day)，请问至少租赁能效 k 为多少的施肥机才能确保不影响收成？如果无法完成施肥任务，则返回 -1。
输入描述：
第一行输入为 m 和 n，m 表示 fields 中的元素个数，n 表示施肥任务必须在 n 天内（含 n 天）完成；
第二行输入为 fields，fields[i] 表示果林i的面积，单位:(m^2)
输出描述：
对于每组数据，输出最小施肥机的能效 k，无多余空格。
补充说明：
1 <= fields.length <= 10^4
1 <= n <= 10^9
1 <= fields[i] <= 10^9
示例1
输入：
5 7
5 7 9 15 10
输出：
9
说明：
当能效k为9时，fields[0] 需要1天，fields[1] 需要1天，fields[2] 需要1天，fields[3] 需要2天，fields[4] 需要2天，共需要7天，不会影响收成。
示例2
输入：
3 1
2 3 4
输出：
-1
说明：
由于一天最多完成一片果林的施肥，无论 k 为多少都至少需要3天才能完成施肥，因此返回-1。
解题思路：
使用二分法。
获取最低能效l=1，获取最高能效（面积最大的果林）r=max
先取中间值mid =（l+r）/2，判断mid是否满足条件。
满足条件判断：ans为需要的天数。
遍历林园面积除以mid，若能整除则ans += 面积/mid，若不能整除，则ans += 面积/mid + 1；若ans<=m（规定天数），则满足，反之不满足。
若mid满足，则r=mid；如不满足，则l=mid+1；继续mid=（l+r）/2进行判断。以此类推，直至l>=r。

代码实现一：

package com.codernav.demo.hwod.exam;

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

/**
 * @title 不爱施肥的小布
 * @Description 某农场主管理了一大片果园，fields[i] 表示不同果林的面积，单位:(m^2)，现在要为所有的果林施肥且必须在 n 天之内完成，否则影响收成。
 * 小布是果林的工作人员，他每次选择一片果林进行施肥，且一片果林施肥完后当天不再进行施肥作业。
 * 假设施肥机的能效为k，单位:(m^2/day)，请问至少租赁能效 k 为多少的施肥机才能确保不影响收成？如果无法完成施肥任务，则返回 -1。
 * @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[] fields = new int[m];
        for (int i = 0; i < m; i++) {
            fields[i] = sc.nextInt();
        }

        int l = 1;  //最低能效
        int r = Arrays.stream(fields).max().getAsInt();     //最高能效
        while (l < r) {
            int mid = (l + r) / 2;      //取中位数
            if (check(mid, fields) <= n) {    //判断能效施肥满足天数要求
                r = mid;    //满足要求，右边界缩小
            } else {
                l = mid + 1;    //不满足，左边界缩小
            }
        }
        if (check(l, fields) > n) {
            System.out.println(-1);
        } else {
            System.out.println(l);
        }
    }

    /**
     * 判断mid能效需要几天完成施肥
     *
     * @param mid    能效
     * @param fields 面积数组
     * @return
     */
    public static int check(int mid, int[] fields) {
        int ans = 0;
        for (int i = 0; i < fields.length; i++) {
            if (fields[i] % mid == 0) {  //能整除能效则直接添加，否则需要+1
                ans += fields[i] / mid;
            } else {
                ans += fields[i] / mid + 1;
            }
        }
        return ans;
    }
}