Loading...
Loading...
Loading...
A courier hub in Pune must send n parcels to a college hostel. The parcels stand in a line and must be loaded in that order. Each day, one truck trip takes the next few parcels, as long as their total weight is at most the truck's capacity. A parcel is never split.
All parcels must reach the hostel within d days. Print the smallest truck capacity that makes this possible.
int holds.Example 1
Input
6 3 3 2 2 4 1 4
Output
6
With capacity 6: day 1 takes 3 2, day 2 takes 2 4, day 3 takes 1 4. Capacity 5 needs four days.
Example 2
Input
4 4 7 1 9 3
Output
9
One parcel per day, so the heaviest parcel decides: 9.
Try the problem first. Open one hint at a time.
Turn the question around: for a fixed capacity, can you easily count the days you need?
Load greedily: keep adding parcels to today's truck until the next one does not fit, then start a new day.
If a capacity works, every larger capacity works too. So search over capacities.
The answer is at least the heaviest parcel and at most the total weight. Use long for both.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor