Binary Search on the Answer

Binary search can optimize a numeric answer without a sorted input array. The requirement is a monotone feasibility test: below some threshold every candidate fails, and at or above it every candidate succeeds. We partition nonnegative job workloads into at most k contiguous groups, minimizing the largest group sum. The array order is fixed; arbitrary reassignment is a different problem.

Prerequisites: Binary Search; functions; greedy reasoning; nonnegative sums.

Build the idea

1. 1. Turn optimization into a yes/no question

   For a candidate maximum workload M, ask whether jobs can be split into at most k contiguous groups, each with sum≤M. If feasible for M, the same grouping remains feasible for every larger limit. This proves a false-to-true predicate. Without nonnegative workloads, the greedy check below would not be valid; monotonicity of the answer alone does not justify an incorrect check.

2. 2. Check feasibility greedily

   Scan left to right, extending the current group while its sum stays within M. Otherwise start a new group. If any single job exceeds M, fail immediately. For nonnegative jobs, extending a group as far as possible cannot force more groups than ending it earlier: every other legal first group ends no later, and the same argument applies to the remaining suffix. Thus this greedy scan minimizes group count for that limit.

3. 3. Establish reliable bounds

   The answer is at least the largest single job, since jobs cannot be split. The total sum is feasible by using one group, so it is a safe upper bound when k≥1. Both are long long. When all jobs are zero, bounds already coincide at zero. n≥1 and 1≤k≤n keep the problem interpretation straightforward; using fewer than k groups is explicitly allowed.

4. 4. Trace a realistic partition

   For jobs [7,2,5,10,8] and k=2, low=10 and high=32. Limit 21 permits [7,2,5] and [10,8]. Limit 15 needs [7,2,5],[10],[8], so it fails. Limit 18 succeeds with sums 14 and 18; limit 17 needs three groups, so the optimum is 18. Search narrows thresholds; it does not sort the jobs.

5. 5. Preserve the first-true invariant

   At each mid, feasibility moves high down to mid; failure moves low up to mid+1. The inclusive candidate interval always contains the smallest feasible value and strictly shrinks. On termination low==high is the optimum. The code’s job scan is the substantive algorithmic component; binary search merely reduces how often it must be evaluated.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Preserve the first-true invariant At each mid, feasibility moves high down to mid;
// failure moves low up to mid+1.
#include<iostream>
#include<vector>
#include<algorithm>
bool feasible(const std::vector<long long>&jobs,int k,long long limit){
    int groups=1;
    long long current=0;
    for(long long job:jobs){
        if(job>limit){
            return false;
        }
        if(current+job>limit){
            ++groups;
            current=0;
        }
        current+=job;
    }
    return groups<=k;
}
int main(){
    int n,k;
    std::cin>>n>>k;
    std::vector<long long>jobs(n);
    long long low=0,high=0;
    for(long long&x:jobs){
        std::cin>>x;
        low=std::max(low,x);
        high+=x;
    }
    while(low<high){
        long long mid=low+(high-low)/2;
        if(feasible(jobs,k,mid)){
            high=mid;
        }
        else{
            low=mid+1;
        }
    }
    std::cout<<low<<'\n';
}

Complexity analysis

O(n log(S+1)) time, where S is total workload (more precisely log of initial bound width plus one), and O(n) input memory with O(1) auxiliary check memory. Each feasibility test is O(n). n≤200000 and 0≤job≤10^9 imply S≤2×10^14, safe in long long.

Example input and output

Read n k (1≤k≤n≤200000), then n nonnegative integer jobs≤10^9 in fixed order. Print the smallest possible maximum sum over at most k nonempty contiguous groups.

Input

5 2
7 2 5 10 8

Output

18

The split after the third job gives sums 14 and 18. A limit of 17 cannot fit the final two jobs together and requires too many groups.

Practical applications

Use for minimum capacity, maximum allowed workload and other threshold optimization problems with a provably correct monotone check. If the check is expensive, analyze its cost multiplied by search iterations. For nonmonotone objectives, use another optimization approach rather than forcing binary search.

Check your understanding

What must be established before binary-searching an answer?

Put it into practice

For n≤10, enumerate all cut positions and compare the optimum.