Kimchi Delivery
InterviewTime limit2sMemory limit128 MB
Given N cities on a line and a starting point, find the order of visiting all cities minimizing the sum of arrival times.
- Level
Medium4 of 10
- Topics
- Greedy, Dynamic programming, Sorting
- Solved
- No attempts yet
Problem
A food company delivers kimchi from one factory to N cities. Every city and the factory lie on a one-dimensional line, each represented by an x-coordinate.
At time 0, the delivery worker starts at the factory position L while carrying N packages of kimchi. Each second, the worker may move one unit left or right. When the worker reaches a city, the kimchi for that city is delivered immediately with no extra time. The cities may be visited in any order.
From time 0, the staleness of each package increases by 1 every second. The staleness of the package delivered to a city is equal to the first time the worker reaches that city. Find the minimum possible sum of staleness values over all cities.
Input
The first line contains two integers N and L. N is the number of cities, and L is the x-coordinate of the kimchi factory. (1 ≤ N ≤ 1,000)
Each of the next N lines contains the x-coordinate of one city that needs a delivery. Every coordinate is an integer between 1 and 1,000,000, inclusive.
Output
Print the minimum possible sum of staleness values after delivering kimchi to every city.