2023 华为od笔试题 0420

笔试时间：2023年4月20日暑期实习

第一题

某农场主管理了一大片果园，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:

5 7

5 7 9 15 10

示例2:

3 1

2 3 4

示例输出

示例1:

9

示例2:

-1

说明：

当能效k为9时，fields[0]需要1天，fields[1]需要1天，fields[2]需要1天，fields[3]需要2天，fields[4]需要2天，一共7天完成，最小的施肥效能为9；由于一天最多完成一片果林的施肥，无论k为多少都至少需要3天才能完成施肥，因此返回-1。

参考题解

二分法

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
using namespace std;

int m, n;
vector<int> fileSizes;

// 检查是否可以将文件放入存储中，以k为最大文件大小
bool canStoreFiles(int k) {
    int currentStorage = 0;
    for (int fileSize : fileSizes) {
        currentStorage += fileSize / k;
        if (fileSize % k != 0) {
            currentStorage += 1;
        }
    }
    return currentStorage <= n;
}

int main() {
    cin >> m >> n;
    fileSizes.resize(m);
    
    for (int i = 0; i < m; i++) {
        cin >> fileSizes[i];
    }

    if (n < m) {
        cout << -1 << endl;
    } else {
        int left = 0, right = 1e9;
        while (left < right) {
            int mid = (left + right) / 2;
            if (canStoreFiles(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        cout << left << endl;
    }
    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    static int m, n;
    static int[] files;

    static boolean check(int k) {
        int cur = 0;
        for (int file : files) {
            cur += file / k;
            if (file % k != 0) {
                cur += 1;
            }
        }
        return cur <= n;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        n = scanner.nextInt();
        files = new int[m];

        for (int i = 0; i < m; i++) {
            files[i] = scanner.nextInt();
        }

        if (n < m) {
            System.out.println(-1);
        } else {
            int l = 0, r = (int) 1e9;
            while (l < r) {
                int mid = (l + r) / 2;
                if (check(mid)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            System.out.println(r);
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def check(k):
    cur = 0
    for file in files:
        cur += file // k
        if file % k != 0:
            cur += 1
    return cur <= n

m, n = map(int, input().split())
files = list(map(int, input().split()))

if n < len(files):
    print(-1)
else:
    l, r = 0, 10**9
    while l < r:
        mid = (l + r) // 2
        if check(mid):
            r = mid
        else:
            l = mid + 1
    print(r)