FireHose (S3)

Question

这个11年级的问题自2010年以来一直困扰着我，即使在大学毕业后，我仍然找不到解决办法。

问题描述 你附近有一条很不寻常的街道。这条街形成一个完美的圆圈，圆周是1,000,000。街上有H (1≤H≤1000)房屋。每栋房子的地址都是从圆的最北端顺时针方向的弧长.房子在圆的最北端的地址是0.你也有特殊的fi软管，沿着街道的曲线。然而，您希望保持最长软管的长度，你需要的最小。您的任务是在这条街上放置k (1≤k≤1000)fi再消防栓，以便将房子与fi再消防栓连接所需的最大软管长度尽可能小。 输入fi阳离子 输入的first行将是整数H，房屋数。下一个H行每一行包含一个整数，这是该特定房屋的地址，每个住宅地址至少为0，小于1,000,000。在H+2线上是数字k，它是可以放置在圆周的fi再消火栓的数目。请注意，fi再消防栓可以放在与房屋相同的位置。你可以假设没有两栋房子在同一个地址。注:这个问题的分数中至少有40%有H≤10。 输出fi阳离子 在一条线上，输出所需的软管长度，使每个房子可以连接到最近的fi再消火栓与该长度的软管。样本输入 4. 0 67000 68000 77000 2 样本输入输出 5000

链接到原始问题

我甚至不能想出一个残酷的强制算法，因为位置可能是浮点数。例如，如果房屋位于1和2，那么水电应该放在1.5，距离是0.5。

Answer 1

这是一个简短的回答大纲。

首先，编写一个函数，该函数可以计算出是否可以覆盖每个消防栓具有给定最大长度的所有房屋。(最大软管长度为该长度的一半。)它只是从一所房子开始，覆盖它所能覆盖的所有房屋，跳到下一所房子，再跳到另一所房子，看看你是否伸展。如果你失败了，它会尝试从下一个房子开始，直到它绕着圆圈走。这将是一个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)