n jobs must be done in the given order by k workers; each worker takes a block of consecutive jobs. What is the smallest possible amount of work for the busiest worker? Binary-search the answer.
Input
The first line has n and k (1 ≤ k ≤ n ≤ 1000). The second line has the n job sizes (each from 1 to 10⁶).
Output
The smallest possible load of the busiest worker.
Examples
Example 1 · Input
5 2 7 2 5 10 8
Expected output
18
Example 2 · Input
3 3 4 9 2
Expected output
9
Hints
Hint 1
works(limit): give jobs in order to a worker until the next would pass limit; count the workers.
Hint 2
A larger limit never needs more workers, so binary search the smallest limit that works.
Hint 3
lo = the largest single job, hi = the sum of all jobs.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<long long> jobs;
bool works(long long limit) {
int workers = 1;
long long load = 0;
for (long long j : jobs) {
if (j > limit) return false;
if (load + j > limit) {
workers++;
load = 0;
}
load += j;
}
return workers <= k;
}
int main() {
cin >> n >> k;
jobs.resize(n);
long long lo = 1, hi = 0;
for (auto& j : jobs) {
cin >> j;
hi += j;
if (j > lo) lo = j;
}
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (works(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
return 0;
}