| Submit | All submissions | Best solutions | Back to list |
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.
| 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 |
hide comments
|
2022-01-22 17:00:31 Buda IM (retired)
Somewhat similar problem is SERVICEH. Very tight TL Last edit: 2022-01-23 09:58:17 |
|
|
2015-09-13 19:18:22 Jens Stimpfle
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. But for most of the problems on SPOJ, if you force yourself to use C, you'll notice how simple the problem actually is and that while C++ might give you memory management and more complex data structures than you want to re-implement in C every time, it also doesn't force you to think through the problem properly. There are so many cases where you don't need a map or a hashtable or a minheap, and you don't need a sort algorithm, or you don't need to materialize certain information. There is often a way to maintain the properties you need as invariants between the iterations of your algorithm. If there is, that's usually the faster way to do it. Last edit: 2015-09-14 16:50:04 |
RSS