Problem Statement
A national broadcasting company, Sacdaorb Inc., needs to upgrade its current system of radio towers to effect minimum cost while retaining coverage of all its customers. Oddly enough, Sacdaorb is run entirely by one-eyed people (who consequently have no depth perception) and its customer base exists in a single straight line. Similarly, their radio towers will all exist in this same straight line to have maximum efficiency. Each tower has an initial cost for the base, which is one meter high, and then an additional cost incurred for each one meter segment above the base. However, the towers can only be built up to a certain maximum height.
The base of a tower by itself will broadcast to the kilometer it is located on, and each additional one meter segment will broadcast an additional one kilometer in all directions. Customers all have buildings that are precisely one kilometer in length, and every part of the building must be broadcast to by a radio tower. See the example for details:
2 T 1 T 0 BBTBB 0123456789 Kilometer
In this example, we have a tower with a base, plus two one meter additions (signified by the T's). The base broadcasts to kilometer 5, the first one meter extension broadcasts to kilometers 4 and 6, and the second extension broadcasts to kilometers 3 and 7. Locations which are broadcast to are signified by B's.
Given a list of the customers' locations, an initial cost for each tower base, and the cost for each additional segment of each tower, determine what the minimum cost is to provide radio service to all customers.
Definition
- Class:
- RadioTower
- Method:
- minCost
- Parameters:
- int[], int, int, int
- Returns:
- int
- Method signature:
- int minCost(int[] customers, int initialcost, int additioncost, int maxheight)
- (be sure your method is public)
Notes
- It is legal to have a radio tower on the same kilometer as a customer
Constraints
- customers will contain between 0 and 50 elements, inclusive.
- Each element of customers will be between 0 and 100000, inclusive.
- initialcost will be between 1 and 1000, inclusive.
- additioncost will be between 1 and 1000, inclusive.
- maxheight will be between 1 and 1000, inclusive.
Examples
{1, 5, 15}
10
2
8
Returns: 24
By placing towers of height 1 (that is, just the base) on kilometers 1, 5, and 15, we cover all customers, and incur a cost of 30. By placing a tower of height 3 on kilometer 3 and a tower of height 1 on kilometer 15, we incur a cost of 2 * 10 + 2 * 2 = 24, and still cover all customers. If we placed a tower of height 8 at kilometer 8, we incur a cost of 1 * 10 + 2 * 7 = 24. Thus, 24 is our minimum cost. Method returns 24.
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
100
100
1
Returns: 2100
{0, 100000, 123, 421, 75236, 34235, 231, 5521, 9871, 98779, 99999, 12415}
1000
1
1000
Returns: 7822
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71}
100
15
4
Returns: 1055
{100000,99000}
1000
1
501
Returns: 1500
{100000,98999}
1000
1
501
Returns: 2000
{20599, 12880, 14586, 14632, 19179, 12407, 31244, 7890, 7270, 22861, 26182, 18886, 29942, 15118, 30859, 28797, 8399, 14107, 2866, 5473, 32591, 29505, 15712, 14068, 28089, 5059, 21027, 22208, 8622, 2605, 25935, 771, 12138}
633
240
246
Returns: 20889
{19260, 26485, 26273, 31204, 4856, 17967, 10112, 17601, 6563, 1227, 28276, 1122, 3920, 29982, 650, 26320, 7651, 10153, 19275, 21725, 6423, 2232, 15785, 15000, 9034, 13119, 11172, 23435, 21263, 5487, 25279, 11963, 9586, 17179, 17702, 32349,18697, 4558, 18844, 18264, 3519, 23208, 3622, 5247, 1376, 32253}
874
1
420
Returns: 23198
{10020, 20953, 22139, 31551, 23166, 1769, 7260, 25287, 29773, 8850, 17486, 21365, 1851, 8454, 1011, 11512, 26361, 30346, 13783, 28826, 3632, 23793, 7996, 8474,30508, 31965, 18083, 17479, 21319, 28341, 10010, 25185, 19735, 20325, 19529, 7983, 16727, 25817, 9018, 18655, 6806, 3639, 3052, 30882, 15266}
711
614
452
Returns: 31995
{27427, 8123, 9740, 16213, 25030, 8690, 23319, 32030, 9526, 3186, 629, 13580, 27017, 10079, 10944, 27580, 29753, 1752, 1536, 29261, 11936, 12733, 5761, 2071}
650
945
823
Returns: 15600
{10364, 23859, 30518, 744, 8416, 22795, 4507, 4899, 11789, 13751, 26522, 8083, 12609, 7203, 3838, 28640, 26942, 25739, 9155, 23978, 8973, 7808, 23851, 22904, 14966, 3515, 22690, 21095, 9786, 10149, 13907, 27791, 3094}, 970, 478, 852
970
47
852
Returns: 31228
{16417, 11968, 11185, 5632, 18020, 409, 2596, 181, 18192, 23643, 20698, 4364, 28020, 28511, 10617, 31385, 14233, 28200, 20208, 23186, 18702, 30780, 15135, 4617, 7792, 13254, 837, 2022, 28091, 30189, 3885, 3750, 16212, 5362, 5912, 27093, 3026, 16396, 5225, 12108, 27280, 30979, 4371, 43, 7411}
958
41
909
Returns: 41809
{7789, 5836, 23854, 16781, 14918, 12246, 8533, 12539, 25153, 24135, 31010, 20055, 6754, 8813, 31774, 19708, 30633, 20336, 30149, 2520, 5611, 16890, 5308, 28667, 3951, 21923}
946
25
64
Returns: 24596
{19129, 15231, 28533, 24869, 3201, 8464, 16313, 18982, 2520, 20124, 31291, 6314, 14595, 3149, 6366, 8330, 5531, 27505, 9822, 15056, 520, 4174, 21039, 17006, 17599, 19625, 26134, 12193, 7483, 22293, 31108, 32291, 11452, 11004, 32437, 18963,11970, 23919, 1421, 20389, 15688, 29357, 20525, 14729}
361
17
464
Returns: 15693
{19412, 10508, 3209, 11089, 21206, 15116, 8144, 29022, 3851, 499, 24432, 7206, 30109, 4967, 4922, 25449, 2648, 9546, 1447, 22958, 1579, 14466, 25784, 12780, 26975, 9349, 21646, 13306, 30100, 20391, 4041, 3005, 19328, 8227}, 704, 331, 343{1477, 22113, 32602, 7472, 31222, 1098, 27183, 22959, 3427, 22409, 11844, 2754,22979, 1037, 20722, 16418, 4660, 3730, 30675, 30589, 5079, 26391, 4276}
323
23
875
Returns: 10774
{30480, 14622, 21, 16115, 26818, 26374, 9488, 23906, 14263, 20511, 15652, 1579,198, 12790, 26907, 7991, 18362, 27776, 10568, 18769, 20005, 7929, 12080, 3677, 2795, 13951, 7669, 14169, 3722, 19053, 25990, 1557, 24618, 25208, 9353, 20146, 8040, 652, 15619}
484
3
244
Returns: 15008
{20679, 11138, 9964, 21175, 8170, 21644, 19286, 5497, 9598, 2149, 30718, 2398, 3765, 2601, 254, 4015, 11963, 17387, 22161, 4832, 18030, 6601, 2345, 20092, 3036, 25015, 29518, 10706, 11648, 3081, 9532, 4445, 19772, 18621, 28220, 31476, 12054}
710
12
945
Returns: 24978
{0,1,2}
100
100
1
Returns: 300
{ }
1
1
1
Returns: 0
{ }
100
10
10
Returns: 0
{ 0, 500, 510, 1010 }
1000
1
251
Returns: 2500