ShipLoading
SRM 415 · 2008-08-26 · by Gluk
SRM 415 · 2008-08-26 · by Gluk · Greedy, Sorting
Problem Statement
Problem Statement
You have to load a ship with some cargo. All the cargo is put in boxes. There are some cranes and each of them can put one box in the ship per minute. All cranes can work simultaneously. Each crane has a weight limit - it cannot move a box whose weight is greater than that limit. Return the minimal time (measured in minutes) needed to load the ship with all cargo or -1 if it is impossible.
You are given aint[] cranes, the i-th element of which is the weight limit of the i-th crane. You are also given a String[] boxes. Concatenate the elements of boxes to get a space-separated list of the boxes' weights.
You are given a
Constraints
- cranes will contain between 1 and 50 elements, inclusive.
- boxes will contain between 1 and 50 elements, inclusive.
- Each element of boxes will contain between 0 and 50 characters, inclusive.
- The concatenation of all elements of boxes will be a non-empty space-separated list of integers with no leading zeroes. It will contain no leading, trailing, or consecutive spaces.
- Each element of cranes will be between 1 and 1,000,000, inclusive.
- Each box weight will be between 1 and 1,000,000, inclusive.
Examples
0)
{6,8,9}
{"2 5 2 4 7"}
Returns: 2
Everything can be done in 2 minutes.
1)
{19,20}
{"14 12 16 19 16 1 5"}
Returns: 4
Only two cranes, but each of them can move any of the boxes.
2)
{23,32,25,28}
{"5 27 10 16 24 20 2 32 18 7"}
Returns: 3
3)
{11,17,5,2,20,7,5,5,20,7}
{"18 18 15 15 17"}
Returns: 2
4)
{687,765,400,19,40,545,986,419,32,1}
{"474 794 982 788 663 608 310 286 316 91 770 902 135"," 237 443 353 490 625 507 8 727 420 668 572 341 362"," 246 622 619 449"}
Returns: 5
10)
{56,114,979,120,120,87,480}
{"221 882 504 358 642 674 212 679 203 279 632 799 79","6 502 275 823 372 594 482 343"}
Returns: 12
Note that you should not add spaces between elements of boxes during their concatenation.
Submissions are judged against all 84 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ShipLoading with a public method int minimumTime(vector<int> cranes, vector<string> boxes) · 84 test cases · 2 s / 256 MB per case