You need to back up computer data for offices situated along single street. You decide to pair off the offices. For each pair of offices you run a network cable between the two buildings so that they can back up each others' data.
However, your local telecommunications company will only give you K network cables, which means you can only arrange backups for K pairs of offices (2K offices in total). No office may belong to more than one pair (that is, these 2K offices must all be different). Furthermore, the telecommunications company charges by the kilometre. This means that you need to choose these K pairs of offices so that you use as little cable as possible.
As an example, suppose you had five offices on a street, situated at distance 1, 3, 4, 6 and 12 from the beginning of the street, and the telecommunications company will provides you with K = 2 cables. The best pairing in this example is created by linking the first and second offices together, and linking the third and fourth offices together. This uses K = 2 cables as required, where the first cable has length 3 – 1 = 2, and the second cable has length 6 – 4 = 2. This pairing requires a total of 4 of network cables, which is the smallest total possible.
Given the locations of N offices and the number of cables K that are made available, compute the cost in cable length of the best K way pairing. (N≤100,000).
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky