Loading...
Loading...
Loading...
The decoration team for the college fest has n pieces of rope with lengths given in metres. They need one long rope for the stage banner. They can join any two pieces into one, and a join takes as many seconds as the total length of the two pieces.
They keep joining until one rope is left. Print the smallest total number of seconds all the joins can take.
Example
Input
4 4 3 2 6
Output
29
Join 2 and 3 (5 seconds), then 4 and 5 (9), then 6 and 9 (15). The total is 29.
Try the problem first. Open one hint at a time.
A piece that is joined early is paid for again in every later join. Which pieces should be joined early?
Always join the two shortest pieces you have right now.
The new piece goes back into the pile. It may not be the longest, so you need to find the two shortest again each time.
A PriorityQueue gives the shortest piece quickly. Keep the lengths and the total in long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor