PROBLEM STATEMENT
You are working backstage at a sold-out rock show. In twenty minutes, your
favorite rock group will emerge onto the stage and perform two hours of the
greatest music ever made. But first, you and your gang of roadies must
transport all the musical equipment and instruments from backstage to the main
stage. The equipment is arranged in a straight line backstage. You are
managing a number of roadies who will actually transport the equipment. Your
job is to simply divide the work in a fair manner - in this case, you decide
that the fairest way to divide the work is to minimize the weight of the
heaviest load carried by a roadie. For example, if there's an amp that weighs
50 pounds, a guitar that weighs 20 pounds, and an instrument cable that weighs
1 pound, and you have two roadies, you want to give one roadie the amp, and
give the other roadie the guitar and the instrument cable - that way, the
heaviest load carried by a roadie is 50 pounds... any other division of labor
would cause one of the roadies to carry more than 50 pounds.
In order to save time and avoid mass confusion, you decide that you will divide
the equipment such that everything carried by any single roadie will be
consecutive items in the line of equipment backstage. For example, if the line
of equipment consists of a bass guitar, followed by a bass amp, followed by a
microphone stand, there is no way you would ever assign the bass guitar and mic
stand to one roadie while assigning the bass amp to another roadie.
You are given a int[] representing the weights of the equipment backstage and
an int representing the number of roadies you have on your team (excluding
yourself - but you won't be carrying any equipment anyway). The int[] of
weights will contain the weights in the order that they appear in the line
backstage. There will be between 0 and 50 pieces of equipment (inclusive)
backstage, and each piece of equipment will weigh between 0 and 1000 pounds
(inclusive). Your team of roadies will contain between 1 and 50 members
(inclusive). Each roadie will carry zero or more pieces of consecutive
equipment. Your solution must return the total weight carried by the roadie
carrying the heaviest load.
DEFINITION
Class name: Roadie
Method name: heaviest
Parameters: int[], int
Returns: int
The method signature is:
int heaviest(int[] weights, int numRoadies);
Be sure your method is public.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
*weights will contain between 0 and 50 elements inclusive
*each element of weights will be between 0 and 1000 inclusive
*numRoadies will be between 1 and 50 inclusive
EXAMPLES
You have a team of three roadies working for Junior Brown. Backstage, you have
the following equipment (from left to right): Guit-steel (15 pounds),
Guit-steel stand (20 pounds), Mic stand (20 pounds), Snare drum (5 pounds),
Upright bass (30 pounds), Acoustic guitar (10 pounds).
You could assign the guit-steel and guit-steel stand to one roadie (15+20=35
pounds). The mic stand and snare drum would go to another roadie (20+5=25
pounds). The upright bass and acoustic guitar would go to the last roadie
(30+10=40 pounds). Any other division would require at least one roadie to
carry more than 40 pounds. The function should return 40 because that is the
minimized heaviest load carried by a single roadie.
Inputs: {15,20,20,5,30,10}, 3
Output: 40
Now, let's say Junior Brown hires four more roadies. In this case, there are
more roadies than pieces of equipment, so we can assign one piece of equipment
to each of six roadies and nothing to the last roadie. There is no way to
minimize the heaviest load below 30 because the heaviest single item is 30
pounds. So, the function should return 30 in this case.
Inputs: {15,20,20,5,30,10}, 7
Output: 30
Finally, for a change of pace, consider a team of six overworked roadies
working for KISS back in 1977. There are, in order, four Marshall stacks (100
pounds each), a Les Paul Custom (25 pounds), an Ibanez Iceman (20 pounds), a
drum set (300 pounds), a Spector bass (20 pounds), fake blood (1 pound), three
mic stands (15 pounds each), four set lists (0 pounds each), two sets of stairs
(500 pounds each), three lifts (600 pounds each), giant flashing logo (200
pounds), confetti (10 pounds), and a dragon totem (20 pounds).
Inputs:
{100,100,100,100,25,20,300,20,1,15,15,15,0,0,0,0,500,500,600,600,600,200,10,20},
6
Output: 830
Some more examples:
Inputs: {1,1,2,1,1}, 3
Output: 2
Inputs: {1,1,2,1,1}, 2
Output: 4
Inputs: {1,1,2,1,1,2,3,3,2,1}, 4
Output: 6
Inputs: {1,1,2,1,1,2,3,3,2,1}, 6
Output: 3