出餐速度speed越大的时候，越可能完成供餐。当取到最值speed = max(nums)时，一定能完成供餐。
对于在区间[1, min(nums)]之间取值的出餐速度speed而言，一定存在一个值ans，使得
- 当speed ∈ [0, ans)时，无法完成供餐。
- 当speed ∈ [ans, max(nums)]时，可以完成供餐。
- 这体现了这个问题的二段性，ans是我们需要的答案，而ans的寻找就可以用二分查找来完成。

子问题分析

对于二分查找过程中得到的每一个出餐速度speed = mid，我们都要去判断在出餐速度的条件下能否完成供餐。

初始化剩余餐数 rest = M，遍历nums数组中每一分钟前来就餐的人数num。若

rest < num，则无法完成供餐，直接返回False。
rest ≥ num，该分钟可以完成供餐，rest要减去当前分钟就餐人数num，同时加上本分钟多提供的餐数speed，用于后续人员的就餐。

上述逻辑整理为代码即构建 check_available(M, nums, speed) 函数

def check_available(M, nums, speed):
    rest = M
    for num in nums:
        if rest < num:
            return False
        rest -= num
        rest += speed
    return True

代码

Python

# 题目：2023B-食堂供餐
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：二分查找
# 代码看不懂的地方，请直接在群上提问


# 该函数用于检查：当选择单位时间出餐份数为 speed 时，能否完成供餐
def check_available(M, nums, speed):
    # 初始化剩余餐数为M
    rest = M
    # 遍历每分钟前来的人数num
    for num in nums:
        # 如果剩余餐数小于本分钟前来人数num
        # 有员工需要等待，无法完成供餐，直接返回False
        if rest < num:
            return False
        # 本分钟可以完成供餐，那么剩余餐数减去就餐人数
        rest -= num
        # 剩余餐数加上该分钟的出餐，可以提供给后续就餐的员工
        rest += speed
    # 在上述循环中没有返回False，说明没有出现员工需要等待的情况
    # 所有人都可以无需等待完成就餐，供餐完成，返回True
    return True


# N分钟
N = int(input())
# 初始已有M份餐
M = int(input())
# N分钟前来就餐的员工数目
nums = list(map(int, input().split()))

# 出餐速度最大值取max(nums)，一定能够满足
# 每个员工都不需要等餐就可以就餐
left, right = 1, max(nums) + 1

# 左闭右开区间，退出循环时存在 left = right = mid
# 循环不变量为left < right
while left < right:
    # 计算 left 和 right 的平均值 mid
    mid = (left + right) // 2
    # 可以完成供餐，说明供餐速度较大，可以缩小，搜索区间向左折半、
    # 退出循环时，存在speed = left = right恰好满足check_available(M, nums, speed)
    if check_available(M, nums, mid):
        right = mid
    else:
        left = mid + 1

# 退出循环时，left = right是恰好可以完成供餐的最小速度
print(left)

Java

import java.util.*;

public class Main {
    // 该函数用于检查：当选择单位时间出餐份数为 speed 时，能否完成供餐
    public static boolean checkAvailable(int M, List<Integer> nums, int speed) {
        // 初始化剩余餐数为 M
        int rest = M;
        // 遍历每分钟前来的人数 num
        for (int num : nums) {
            // 如果剩余餐数小于本分钟前来人数 num
            // 有员工需要等待，无法完成供餐，直接返回 false
            if (rest < num) {
                return false;
            }
            // 本分钟可以完成供餐，那么剩余餐数减去就餐人数
            rest -= num;
            // 剩余餐数加上该分钟的出餐，可以提供给后续就餐的员工
            rest += speed;
        }
        // 在上述循环中没有返回 false，说明没有出现员工需要等待的情况
        // 所有人都可以无需等待完成就餐，供餐完成，返回 true
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // N 分钟
        int N = scanner.nextInt();
        // 初始已有 M 份餐
        int M = scanner.nextInt();
        // N 分钟前来就餐的员工数目
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            nums.add(scanner.nextInt());
        }

        // 出餐速度最大值取 max(nums)，一定能够满足
        // 每个员工都不需要等餐就可以就餐
        int left = 1, right = Collections.max(nums) + 1;

        // 左闭右开区间，退出循环时存在 left = right = mid
        // 循环不变量为 left < right
        while (left < right) {
            // 计算 left 和 right 的平均值 mid
            int mid = (left + right) / 2;
            // 可以完成供餐，说明供餐速度较大，可以缩小，搜索区间向左折半、
            // 退出循环时，存在 speed = left = right 恰好满足 checkAvailable(M, nums, speed)
            if (checkAvailable(M, nums, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        // 退出循环时，left = right 是恰好可以完成供餐的最小速度
        System.out.println(left);
    }
}

C++

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

// 该函数用于检查：当选择单位时间出餐份数为 speed 时，能否完成供餐
bool checkAvailable(int M, vector<int>& nums, int speed) {
    // 初始化剩余餐数为 M
    int rest = M;
    // 遍历每分钟前来的人数 num
    for (int num : nums) {
        // 如果剩余餐数小于本分钟前来人数 num
        // 有员工需要等待，无法完成供餐，直接返回 false
        if (rest < num) {
            return false;
        }
        // 本分钟可以完成供餐，那么剩余餐数减去就餐人数
        rest -= num;
        // 剩余餐数加上该分钟的出餐，可以提供给后续就餐的员工
        rest += speed;
    }
    // 在上述循环中没有返回 false，说明没有出现员工需要等待的情况
    // 所有人都可以无需等待完成就餐，供餐完成，返回 true
    return true;
}

int main() {
    // N 分钟
    int N;
    cin >> N;
    // 初始已有 M 份餐
    int M;
    cin >> M;
    // N 分钟前来就餐的员工数目
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }

    // 出餐速度最大值取 *max_element(nums.begin(), nums.end())，一定能够满足
    // 每个员工都不需要等餐就可以就餐
    int left = 1, right = *max_element(nums.begin(), nums.end()) + 1;

    // 左闭右开区间，退出循环时存在 left = right = mid
    // 循环不变量为 left < right
    while (left < right) {
        // 计算 left 和 right 的平均值 mid
        int mid = (left + right) / 2;
        // 可以完成供餐，说明供餐速度较大，可以缩小，搜索区间向左折半、
        // 退出循环时，存在 speed = left = right 恰好满足 checkAvailable(M, nums, speed)
        if (checkAvailable(M, nums, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    // 退出循环时，left = right 是恰好可以完成供餐的最小速度
    cout << left << endl;

    return 0;
}

时空复杂度

时间复杂度：O(NlogC)。

C = max(nums)为就餐人数数组nums中的最大值。
子问题单次求解即函数check_available(M, nums, speed)时间复杂度为O(N)
二分查找算法的时间复杂度为O(logC))。每次都需要调用check_available()函数，故总的二分查找时间复杂度度为O(NlogC))

空间复杂度：O(1)。