Binary search is not only for arrays. Here it searches over possible answers.
What to build
A program that finds the smallest truck capacity that can carry all the parcels in at most d trips.
Requirements
- Parcels must be carried in the order given, and a parcel cannot be split.
- Write a function that counts the trips needed for a given capacity.
- Binary search on the capacity, from the heaviest parcel up to the total weight.
Input
The first line has n and d. The second line has the n weights.
Output
The smallest capacity that needs at most d trips.
Constraints
1 ≤ d ≤ n ≤ 500, and each weight is from 1 to 1000.
Example
Input:
5 2
3 2 2 4 1
Output:
7
Why it works
The test "can capacity c do it?" is no for small c and yes for large c, with one switch-over point. Binary search finds that point with about log₂(total weight) checks, each taking O(n).
Examples
5 2 3 2 2 4 1
7
10 5 1 2 3 4 5 6 7 8 9 10
15
Hints
Hint 1
If a capacity works, every larger capacity also works. That is what lets you binary search on the answer.
Hint 2
Write a function that takes a capacity and counts how many trips it needs, filling each trip until the next parcel does not fit.
Hint 3
The capacity is at least the heaviest parcel, and at most the total weight.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int trips(int w[], int n, int capacity) {
int count = 1, load = 0;
for (int i = 0; i < n; i++) {
if (load + w[i] > capacity) {
count++;
load = 0;
}
load += w[i];
}
return count;
}
int main(void) {
int n, d, w[500];
scanf("%d %d", &n, &d);
int lo = 0, hi = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
if (w[i] > lo) lo = w[i];
hi += w[i];
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (trips(w, n, mid) <= d) hi = mid;
else lo = mid + 1;
}
printf("%d\n", lo);
return 0;
}