The fast food chain, McBurger, has recently consolidated all activities to restaurants along the Trans Canada Highway. (Following the completion of fixed links joining Newfoundland and Vancouver Island to the mainland.) They have also decided to build several warehouses along the highway, each located at a restaurant and supplying those restaurants nearby. Naturally, these warehouses should be placed so as to minimize the distance between the warehouses and the restaurants they service. Your task is to write a program that determines the optimal positions for the warehouses.
To make the problem more precise, chairman McBoss has issued the following specification: You are given the positions of n restaurants across the country as n integers d1 < d2 < ... < dn. These integers are the distances, in kilometres, from the company's new headquarters in St. John's, at the extreme Eastern end of the highway. You are also given the number k <= n, the number of warehouses to be constructed. You are to place the warehouses at the locations of k of the n restaurants so as to minimize the maximum distance from any restaurant to its nearest warehouse.
6 3 5 6 12 19 20 27 0
6 20 27 6