Problem Statement | | | Cucumberman planted N cucumbers along a straight road. Cucumbers are numbered 0 through N-1, and the position of the i-th cucumber is x[i]. The cucumbers are at pairwise distinct coordinates, but their coordinates are not necessarily in sorted order. He waters all cucumbers every day. He can't change the order of watering cucumbers, so he must water cucumber 0 first, water cucumber 1 next, and so on. (Note that this means he may be going back and forth along the road.)
Watering a cucumber takes zero time. When walking, Cucumberman needs one unit of time to travel one unit of distance. Additionally, he can build at most K teleports at any positions (including non-integer ones). If there are teleports at both P and Q, he can move from P to Q instantly using teleports.
He wants to minimize the duration between watering cucumber 0 and watering cucumber N-1. Return this minimum time, assuming that he builds and uses the K teleports optimally.
| | | Definition | | | | Class: | CucumberWatering | | Method: | theMin | | Parameters: | int[], int | | Returns: | long | | Method signature: | long theMin(int[] x, int K) | | (be sure your method is public) |
| | | | | | Constraints | | - | x will contain between 2 and 50 elements, inclusive. | | - | Each element of x will be between -1,000,000,000 (-10^9) and 1,000,000,000 (10^9), inclusive. | | - | Elements of x will be pairwise distinct. | | - | K will be between 1 and 50, inclusive. | | | Examples | | 0) | | | | | Returns: 6 | One optimal way is as follows:
- Build teleports at 1 and 7.
- Water cucumber 0 at 0. Walk to 1, teleport to 7, walk to 6 and water cucumber 1. Walk to 8 and water cucumber 2. Walk to 7, teleport back to 1, walk to 2 and water cucumber 3.
It takes |0-1| + |7-6| + |6-8| + |8-7| + |1-2| = 6 unit time in total.
|
|
| | 1) | | | | {-1000000000, 1000000000, 0} | 1 |
| Returns: 3000000000 | | Only one teleport is useless. |
|
| | 2) | | | | | | 3) | | | | {9, -3, 14, 6, 5, -9, 32, 7, -5, 26, 2, 11} | 3 |
| Returns: 58 | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
|
