TWODEL - Delivery
Fast Delivery Corporation built one of its offices right in the middle of the longest straight street in Cuba in order to satisfy every order of those customers who live along that street.
The addresses of the houses to which the merchandises are distributed are represented by integer numbers which represent the distance between the office and the corresponding houses. If we consider that the office is located at position 0, then the positive addresses are located to the right of the office, and the negative addresses are located to the left of the office.
The delivery orders are satisfied in the same order in which they were received.
Fast Delivery Corporation has assigned two employees to the new office. Those employees are in charge of distributing the merchandises. At the beginning of the day, the orders are shared between both employees.
The corporation wants to share the orders between the two employees in such a way that the total distance required to deliver all the merchandise is minimized.
Input
Line 1: a single integer N (1 <= N <= 100,000) representing the number of orders
The next N lines contain an integer representing an address where a merchandise will be delivered.
The distance between the office and any house is not greater than 108
Output
A single line: the minimum distance the two employees have to travel to satisfy every order.
Example
Input: 5 1 -1 2 -2 3 Output: 5
Note: The naive greedy doesn't work. Also remember that the deliveries must be satisfied in the same order they appear in the input.
hide comments
Buda IM (retired):
2022-01-22 17:00:31
Somewhat similar problem is SERVICEH. Very tight TL Last edit: 2022-01-23 09:58:17 |
|
Jens Stimpfle:
2015-09-13 19:18:22
Having thought about a problem, so often I have thought I should use C++, because map, or because whatever feature that's so important to tame the apparent complexity of the problem.
|
Added by: | Angel Paredes |
Date: | 2012-02-12 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 PERL6 |
Resource: | Cuban Olympiad in Informatics 2011 - Day 1 Problem B |