 def sub_question(k, nums, m, N):
    ans = 0
    check = [0] * m
    for i in range(m):
        if check[i] == 1:
            continue
        ans += 1
        cur_sum = 0
        j = i
        while j < m:
            if check[j] == 1:
                j += 1
                continue
            if nums[j] + cur_sum > k:
                j += 1
            else:
                cur_sum += nums[j]
                check[j] = 1
                j += 1
    return ans <= N

初始化左闭右开区间left = max(nums)，right = sum(nums) + 1，进行二分。

计算mid = (left + right) // 2。当

sub_question(mid, nums, m, N)为True时，说明当选择了阈值k = mid时，可以将任务分配给N个人（组数小于等于N）。此时的mid的选择偏大，区间应该左移，right左移。
sub_question(mid, nums, m, N)为False时，说明当选择了阈值k = mid时，无法将任务分配给N个人（组数大于N）。此时的mid的选择偏小，区间应该右移，left右移。

故结合贪心子问题，整体的二分代码为

nums = list(map(int, input().split()))
m = len(nums)
N = int(input())
nums.sort(reverse = True)
left, right = max(nums), sum(nums)+1
while left < right:
    mid = (right + left) // 2
    if sub_question(mid, nums, m, N):
        right = mid
    else:
        left = mid + 1
        
print(left)

代码

Python

# 题目：【二分查找】2024E-项目排期
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：二分查找/贪心
# 代码看不懂的地方，请直接在群上提问
# 相关题目：【贪心】2023B-数据最节约的备份方法


# 贪心子问题，当选择了阈值k时，如果m个任务nums可以被分配给N个员工，
# 且每一个员工的工作总量不超过k则返回True，否则返回False
# （注意此处nums必须是一个已排序好的逆序数组）
# 该子问题的时间复杂度与nums的长度m相关，为O(m^2)
def sub_question(k, nums, m, N):
    ans = 0
    # 初始化长度为m的check数组，用来表示第i个任务是否已经分配给了某一个员工
    check = [0] * m
    # 遍历所有nums每一个工作量
    for i in range(m):
        # 如果该工作已经由某个员工完成了，则直接跳过
        if check[i] == 1:
            continue
        # 否则，需要一个新的员工
        # 来完成包含工作nums[i]在内的若干工作
        # 故ans更新
        ans += 1
        # 初始化当前员工所做的工作总量为0
        cur_sum = 0
        # 初始化变量j为i，用于修改当前这个员工的工作情况
        j = i
        # 进行内层循环，此处涉及贪心算法
        while j < m:
            # 如果第j个工作已经安排，则j直接递增，跳过第j个工作
            if check[j] == 1:
                j += 1
                continue
            # 如果第j份工作和当前员工之前的工作量之和超过k
            # 则这个员工不能选择这份工作，j递增
            if nums[j] + cur_sum > k:
                j += 1
            # 如果第j份工作和当前员工之前的工作量之和不超过k
            # 则贪心地将这份工作安排给这个员工
            # 修改cur_sum和check[j]，j递增
            else:
                cur_sum += nums[j]
                check[j] = 1
                j += 1
    # 退出循环时，如果需要的人数ans不超过N，则返回True，否则返回False
    return ans <= N


# 输入m个任务构成的数组
nums = list(map(int, input().split()))
# 获得nums的长度，即任务数量
m = len(nums)
# 输入员工人数N
N = int(input())
# 对nums进行逆序排序，方便后续贪心子问题的计算
nums.sort(reverse = True)
# 初始化左闭右开
left, right = max(nums), sum(nums)+1
while left < right:
    mid = (right + left) // 2
    # 如果选择了mid作为阈值，可以将任务分配给N个人（组数小于等于N）
    # 说明mid的选择偏大，区间应该左移，right左移
    if sub_question(mid, nums, m, N):
        right = mid
    # 如果选择了mid作为阈值，无法将任务分配给N个人（组数多于N）
    # 说明mid的选择偏小，区间应该右移，left右移
    else:
        left = mid + 1

# 退出循环时，存在left = right是恰好可以将任务分配给N个人的阈值k
# left或right即为答案
print(left)

Java

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

public class Main {
    // 贪心子问题
    private static boolean subQuestion(int k, int[] nums, int m, int N) {
        int ans = 0;
        int[] check = new int[m];

        for (int i = 0; i < m; i++) {
            if (check[i] == 1) continue;
            ans++;
            int curSum = 0;
            int j = i;
            while (j < m) {
                if (check[j] == 1) {
                    j++;
                    continue;
                }
                if (nums[j] + curSum > k) {
                    j++;
                } else {
                    curSum += nums[j];
                    check[j] = 1;
                    j++;
                }
            }
        }
        return ans <= N;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入m个任务构成的数组
        String[] numsStr = scanner.nextLine().split(" ");
        int m = numsStr.length;
        int[] nums = new int[m];
        for (int i = 0; i < m; i++) {
            nums[i] = Integer.parseInt(numsStr[i]);
        }

        // 输入员工人数N
        int N = scanner.nextInt();

        // 对nums进行逆序排序
        Arrays.sort(nums);
        for (int i = 0; i < m / 2; i++) {
            int temp = nums[i];
            nums[i] = nums[m - i - 1];
            nums[m - i - 1] = temp;
        }

        // 初始化左闭右开
        int left = nums[0], right = Arrays.stream(nums).sum() + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (subQuestion(mid, nums, m, N)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        // 输出结果
        System.out.println(left);
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <numeric>

using namespace std;

bool subQuestion(int k, vector<int>& nums, int m, int N) {
    int ans = 0;
    vector<int> check(m, 0);

    for (int i = 0; i < m; i++) {
        if (check[i] == 1) continue;
        ans++;
        int curSum = 0;
        int j = i;
        while (j < m) {
            if (check[j] == 1) {
                j++;
                continue;
            }
            if (nums[j] + curSum > k) {
                j++;
            } else {
                curSum += nums[j];
                check[j] = 1;
                j++;
            }
        }
    }
    return ans <= N;
}

int main() {
    vector<int> nums;
    string input;
    getline(cin, input);
    stringstream ss(input);
    int num;
    while (ss >> num) {
        nums.push_back(num);
    }
    int m = nums.size();
    int N;
    cin >> N;

    sort(nums.begin(), nums.end(), greater<int>());
    int left = nums[0], right = accumulate(nums.begin(), nums.end(), 0) + 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (subQuestion(mid, nums, m, N)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    cout << left << endl;
    return 0;
}

时空复杂度

时间复杂度：O(log(C)m^2)。贪心子问题的时间复杂度为O(m^2)，二分查找的时间复杂度为O(logC)，其中C = sum(nums) - max(nums)。

空间复杂度：O(m)。贪心子问题需要构建长度为m的check数组。