刷题笔记合集🔗

问题描述

某农场主管理了一大片果园,fields[i]表示不同果林的面积(单位:m²)。现在要为所有果林施肥,且必须在n天内完成,否则影响收成。

小布是果林的工作人员,他每次选择一片果林进行施肥,且一片果林施肥完后当天不再进行施肥作业。

假设施肥机的能效为k(单位:m²/day),请问至少租赁能效k为多少的施肥机才能确保不影响收成?如果无法完成施肥任务,则返回-1。

输入格式

第一行输入两个整数m和n:

• m表示果林数量
• n表示施肥任务必须在n天内(含n天)完成

第二行输入m个整数,表示每片果林的面积。

输出格式

输出一个整数,表示最小施肥机的能效k。如果无法完成任务,输出-1。

数据范围

• 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]=5需要1天
  • fields[1]=7需要1天
  • fields[2]=9需要1天
  • fields[3]=15需要2天
  • fields[4]=10需要2天
• 共需要7天,不会影响收成

样例2

输入:

3 1
2 3 4

输出:

-1

说明:

• 一天最多完成一片果林的施肥
• 3片果林至少需要3天
• 无论k为多少都无法在1天内完成
• 所以返回-1

题解

这道题目可以使用二分查找来解决:

1. 确定k的搜索范围:
   • 最小值为1
   • 最大值为max(fields)
2. 二分查找k:
   • 对于每个k,计算完成所有果林需要的天数
   • 如果天数>n,说明k太小
   • 如果天数≤n,说明k可能是答案
3. 找到满足条件的最小k

时间复杂度为 ,其中 是果林数量, 是最大果林面积。

参考代码

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

def check(k, n, fields):
    # 计算能效k完成所有果林需要的天数
    days = 0
    for area in fields:
        if k >= area:
            days += 1  # 面积小于能效,一天完成
        else:
            days += (area + k - 1) // k  # 向上取整
    return days <= n

def solve(n, fields):
    if len(fields) > n:  # 果林数量大于天数,无解
        return -1
        
    left, right = 1, max(fields)
    ans = -1
    
    while left <= right:
        mid = (left + right) // 2
        if check(mid, n, fields):
            ans = mid
            right = mid - 1  # 尝试更小的k
        else:
            left = mid + 1
            
    return ans

print(solve(n, fields))

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();