刷题笔记合集🔗

农场施肥

问题描述

小柯管理了一大片果园， 表示不同果林的面积，单位：，现在要为所有的果林施肥且必须在 天之内完成，否则影响收成。小基 是果林的工作人员，他每次选择一片果林进行施肥，且一片果林施肥完后当天不再进行施肥作业。

假设施肥机的能效为 ，单位：，请问至少租赁能效 为多少的施肥机才能确保不影响收成？如果无法完成施肥任务，则返回 。

输入格式

第一行输入为 和 ， 表示 中的元素个数， 表示施肥任务必须在 天内（含 天）完成。

第二行输入为 ， 表示果林 的面积，单位：。

输出格式

对于每组数据，输出最小施肥机的能效 ，无多余空格。

样例输入

5 7
5 7 9 15 10

3 1
2 3 4

样例输出

9

-1

数据范围

样例	解释说明
样例1	当能效k为9时，fields[0]需要1天，fields[1]需要1天，fields[2]需要1天，fields[3]需要2天，fields[4]需要2天，共需要7天，不会影响收成。
样例2	由于一天最多完成一片果林的施肥，无论k为多少都至少需要3天才能完成施肥，因此返回-1。

• 
• 
• 

题解

这道题目的核心是寻找最小的施肥机能效 k，使得能在规定的 n 天内完成所有果林的施肥。

首先明确一点：如果果林数量大于可用天数，那么无论施肥机能效多高，都无法完成任务（因为一天只能处理一片果林），此时应返回 -1。

解题的思路是使用二分查找来找到最小的满足条件的 k 值：

1. 确定 k 的搜索范围：最小值是 1（至少能施肥 1 平方米/天），最大值是所有果林中最大的面积（因为超过这个值不会带来更多优势）。
2. 对于每个尝试的 k 值，计算完成所有果林施肥需要的天数，判断是否不超过 n 天。
3. 如果当前 k 值可以完成任务，我们尝试减小 k 值；如果不能完成，则增大 k 值。

关于每片果林需要几天施肥的计算：

• 如果果林面积小于等于 k，则只需要 1 天
• 如果果林面积大于 k，则需要 ⌈面积/k⌉ 天（向上取整）

时间复杂度分析：

• 二分查找的次数是 O(log(max_field))，其中 max_field 是最大的果林面积（不超过 10^9）
• 每次二分查找需要遍历所有果林计算总天数，复杂度为 O(m)
• 总时间复杂度为 O(m * log(max_field))，对于给定的约束（m ≤ 10^4, max_field ≤ 10^9），这是可以接受的

这种二分查找的思路非常适用于求解「最大值最小化」或「最小值最大化」类型的问题，尤其是当直接计算答案困难但验证某个答案是否可行较容易时。

参考代码

• Python

import sys
import math
input = lambda:sys.stdin.readline().strip()

# 读取输入
m, n = map(int, input().split())
fields = list(map(int, input().split()))

# 如果果林数量大于可用天数，无法完成任务
if m > n:
    print(-1)
    exit(0)

def check_feasible(k):
    """检查能效为k时是否能在n天内完成施肥"""
    days = 0
    for area in fields:
        # 一片果林需要的天数：1天或ceil(area/k)天
        days += math.ceil(area / k)
    return days <= n

# 二分查找最小的k
def binary_search():
    # 能效k的范围：1到最大果林面积
    left = 1
    right = max(fields)
    best_k = -1
    
    while left <= right:
        mid = (left + right) // 2
        if check_feasible(mid):
            # 可行，尝试更小的k
            best_k = mid
            right = mid - 1
        else:
            # 不可行，需要更大的k
            left = mid + 1
    
    return