TopCoder problem "LibraryWorker" used in TCHS SRM 40 (Division I Level Two)



Problem Statement

    You work in a large library. It is the end of the day and you have to replace a number of returned books back on the shelves. The shelves are located at integer positions (positive and negative) along a long corridor and the pile of books is located at position 0. You start off standing at the pile of books (position 0). You can carry at most N books at a time and want to know the minimum total distance that you will have to walk in order to replace all the books.



You are given a int[] books, where each element describes the position of the shelf where a single book must be returned. Return the minimum total distance that you have to walk to replace all the books. You do not need to return to the pile of books after you have finished.
 

Definition

    
Class:LibraryWorker
Method:replaceBooks
Parameters:int[], int
Returns:int
Method signature:int replaceBooks(int[] books, int N)
(be sure your method is public)
    
 

Constraints

-books will contain between 1 and 50 elements, inclusive.
-Each element of books will be between -10,000 and 10,000, inclusive.
-The elements of books will be distinct.
-No element of books will be 0.
-N will be between 1 and 50, inclusive.
 

Examples

0)
    
{-37,2,-6,-39,-29,11,-28}
2
Returns: 131
First replace the book going to position -6 on its own and then return to the pile at 0. This requires you to walk a distance of 12.

Then pick up the books going to 2 and 11. You walk past shelf 2 on the way to 11, so you have to walk a total distance of 22.

Now replace books -28 and -29. The distance walked is 58.

Finally replace books -37 and -39. Since you don't have to return to 0, you only need to walk 39 units.

Total distance = 12 + 22 + 58 + 39 = 131
1)
    
{-18,-9,-4,50,22,-26,40,-45}
3
Returns: 158
An optimal schedule could be:

-4, -9 : distance 18

-18, -26, -45 : distance 90

22, 40, 50 : distance 50

Total distance = 158
2)
    
{-6980,443,-3134,-6639,-65,-142,4688,-8323,-5966,1308,-5241,-3799,-8091
,-6388,-7974,-5682,1820,-6516,-879,-3677,-266,9308,5250,-4418,-8052,6935
,-9134,-5068,-835,5396,7262,6579,-7672,-3723,-6781,-9466,327,4973,2066,3418}
6
Returns: 73920
3)
    
{3, 4, 5, 6, 11, -1}
2
Returns: 29
4)
    
{1}
50
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8054

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10784&pm=8054

Writer:

StevieT

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Greedy, Simulation