algorithm - CCC 的 FireHose (S3)

Question

这个 11 年级的问题自 2010 年以来一直困扰着我，即使在大学毕业后我仍然无法弄清楚/找到解决方案。

Problem Description

There is a very unusual street in your neighbourhood. This street forms a perfect circle, and the circumference of the circle is 1,000,000. There are H (1 ≤ H ≤ 1000) houses on the street. The address of each house is the clockwise arc-length from the northern-most point of the circle. The address of the house at the northern-most point of the circle is 0. You also have special firehoses which follow the curve of the street. However, you wish to keep the length of the longest hose you require to a minimum. Your task is to place k (1 ≤ k ≤ 1000) fire hydrants on this street so that the maximum length of hose required to connect a house to a fire hydrant is as small as possible.

Input Specification

The first line of input will be an integer H, the number of houses. The next H lines each contain one integer, which is the address of that particular house, and each house address is at least 0 and less than 1,000,000. On the H + 2nd line is the number k, which is the number of fire hydrants that can be placed around the circle. Note that a fire hydrant can be placed at the same position as a house. You may assume that no two houses are at the same address. Note: at least 40% of the marks for this question have H ≤ 10.

Output Specification
On one line, output the length of hose required so that every house can connect to its nearest fire hydrant with that length of hose.

Sample Input
4
0
67000
68000
77000
2

Output for Sample Input
5000

Link to original question

我什至无法想出一个残酷的算法，因为放置可能是 float 。例如，如果房屋位于 1 和 2，则水电应位于 1.5，距离为 0.5

Answer 1

这里是答案的简要概述。

首先编写一个函数，计算是否可以覆盖每个消防栓具有给定最大长度的所有房屋。 (最大软管将是该长度的一半。)它只是从一个房子开始，覆盖所有它能覆盖的房子，跳到下一个，同上，看你是否拉伸(stretch)。如果你失败了，它会尝试从下一个房子开始，直到它绕完圈。这将是一个 O(n^2) 函数。

其次创建房屋之间成对距离的排序列表。 (对于一个消防栓，你必须考虑它是双向的，如果你有 2 个以上的消防栓，你只能担心较短的方法。)消防栓覆盖的长度将是其中之一。这需要 O(n^2 log(n))。

现在进行二分查找，找到可以覆盖所有房屋的最短长度。这将需要 O(log(n)) 调用您在第一步中编写的 O(n^2) 函数。

最终结果是一个O(n^2 log(n)) 算法。

这里是除解析逻辑之外的所有工作代码。

#! /usr/bin/env python

def _find_hoses_needed (circle_length, hose_span, houses):
    # We assume that houses is sorted.
    answers = [] # We can always get away with one hydrant per house.
    for start in range(len(houses)):
        needed = 1
        last_begin = start
        current_house = start + 1 if start + 1 < len(houses) else 0
        while current_house != start:
            pos_begin = houses[last_begin]
            pos_end = houses[current_house]
            length = pos_end - pos_begin if pos_begin <= pos_end else circle_length + pos_begin - pos_end
            if hose_span < length:
                # We need a new hose.
                needed = needed + 1
                last_begin = current_house
            current_house = current_house + 1
            if len(houses) <= current_house:
                # We looped around the circle.
                current_house = 0
        answers.append(needed)
    return min(answers)

def find_min_hose_coverage (circle_length, hydrant_count, houses):
    houses = sorted(houses)

    # First we find all of the possible answers.
    is_length = set()
    for i in range(len(houses)):
        for j in range(i, len(houses)):
            is_length.add(houses[j] - houses[i])
            is_length.add(houses[i] - houses[j] + circle_length)
    possible_answers = sorted(is_length)

    # Now we do a binary search.
    lower = 0
    upper = len(possible_answers) - 1
    while lower < upper:
        mid = (lower + upper) / 2 # Note, we lose the fraction here.
        if hydrant_count < _find_hoses_needed(circle_length, possible_answers[mid], houses):
            # We need a strictly longer coverage to make it.
            lower = mid + 1
        else:
            # Longer is not needed
            upper = mid
    return possible_answers[lower]

print(find_min_hose_coverage(1000000, 2, [0, 67000, 68000, 77000])/2.0)