Problem Statement |
| | There are several guideposts on one side of a highway indicating the distance to a gas station that has not yet been built. Unfortunately, the guideposts are not synchronized, so they might not all refer to the same location. You must build the gas station at a location that will minimize the cost of moving the guideposts to their correct positions. It costs one dollar per kilometer to move each guidepost. In addition, there is a limit to how far each guidepost can be moved without incurring further taxes. If a guidepost is moved further than than its limit, it costs an additional C dollars for each kilometer that exceeds the limit.
You are given a String[] guideposts, each element of which describes a single guidepost. Each element is formatted as "position distance limit" (quotes for clarity only), where position is a nonnegative integer specifying the location of the guidepost relative to the entry point of the highway, distance is an integer specifying the distance to the gas station that's written on the guidepost (negative values mean that the guidepost is located beyond the gas station), and limit is a nonnegative integer specifying the maximum distance the guidepost can be moved without paying further taxes. All values are given in kilometers. The position of the gas station relative to the entry point of the highway must be a nonnegative integer. Return the minimum cost of moving the guideposts as a long. |
| |
Definition |
| | | Class: | SynchronizingGuideposts | | Method: | minCost | | Parameters: | String[], int | | Returns: | long | | Method signature: | long minCost(String[] guideposts, int C) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Since the position of the gas station has to be a nonnegative integer, there is no need to move a guidepost by a fractional amount. |
| |
Constraints |
| - | guideposts will contain between 1 and 50 elements, inclusive. |
| - | Each element of guideposts will contain between 5 and 50 characters, inclusive. |
| - | Each element of guideposts will be formatted as described in the problem statement. |
| - | Each position will be an integer between 1 and 1,000,000,000, inclusive. |
| - | Each distance will be an integer between -1,000,000,000 and 1,000,000,000, inclusive. |
| - | Each limit will be an integer between 0 and 1,000,000,000, inclusive. |
| - | Each position, distance, and limit may include leading zeros. |
| - | C will be between 1 and 1000, inclusive. |
| |
Examples |
| 0) | |
| | {"6 -1 5","2 10 4","10 0 5","8 6 5","20 -6 4"} | 1000 |
| Returns: 15 | | With C being so high, we better make sure that none of the guideposts are moved beyond their limits. We can do this by placing the gas station at position 10. |
|
|
| 1) | |
| | {"59 23 13","9 8 28","91 18 50","32 10 80","110 61 120","54 45 18","73 24 118","30 8 73"} | 5 |
| Returns: 479 | | Placing the gas station at position 81 yields the optimum cost. |
|
|
| 2) | |
| | {"79 4 114","68 41 102","80 80 68","48 1 50","59 17 34","118 59 17","29 3 11","31 26 48","74 27 2"} | 46 |
| Returns: 5731 | |
|
| 3) | |
| | {"1 -2 10","2 -3 20","3 -4 30","4 -5 40","5 -6 50"} | 333 |
| Returns: 5 | | Interestingly, all guideposts refer to the same position. Since this position is slightly off the highway, you should move each guidepost one kilometer. |
|
|