[已解决]二分答案：马拉松

刘子诺

马拉松(marathon)
1.0s 256MB
题目描述
环湖马拉松全程L公里，已经安排了N个补给点，位置已经确定。由于预算增加，现在可以增设K个补给点。如何安排新增的补给点使得相邻补给点间最大距离最小。相邻补给点间距离也包括起点与第一个补给点之间的距离和最后一个补给点与终点之间的距离。

输入格式
第一行包括整个整数L、N、K，分别表示马拉松全程长度、原有补给点的数量以及最多可以增设的补给点的数量。
第二行，N个整数，表示原有的N个补给点的位置。补给点的位置用距离起点的距离表示，取值范围(0，L)。

输出格式
一个整数，意义如题所述,表示相邻补给点间最大距离最小值

样例
输入数据#1
100 2 1
70 30
Copy
输出数据#1
30
Copy
数据范围
0<N<=100000
0<=L<=2000000000
0<=K<=2000000000

知道是二分答案，但是在不知道应该怎么写，求助！

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-8 20:58:42

二分答案是一种常用的算法技巧，可以用来解决一些满足某种性质的问题。对于这道题目，我们可以使用二分答案来确定新增的补给点使得相邻补给点间最大距离最小。

首先，我们可以观察到，相邻补给点间最大距离的取值范围是在0到L之间。我们可以将这个范围作为二分的上下界。

然后，我们需要编写一个函数来判断给定的距离是否满足条件。我们可以遍历原有的补给点，计算相邻补给点间的距离，如果有任意两个相邻补给点间的距离大于给定的距离，则说明当前的距离不满足条件。

接下来，我们可以使用二分搜索来找到满足条件的最小距离。我们设定二分搜索的初始上下界分别为0和L，然后进行循环，直到上下界相等。在每一次循环中，我们计算中间值mid，并调用判断函数判断mid是否满足条件。如果满足条件，说明我们可以继续缩小距离，将上界更新为mid；如果不满足条件，说明距离太小，需要增加距离，将下界更新为mid+1。

最后，当上下界相等时，说明我们找到了满足条件的最小距离，即为答案。

下面是具体的代码实现：

def check_distance(distance, L, N, K, supply_points):
    count = 0
    prev_point = 0
    for point in supply_points:
        count += (point - prev_point) // distance
        prev_point = point
    count += (L - prev_point) // distance
    return count >= N + K

def binary_search(L, N, K, supply_points):
    left = 0
    right = L
    while left < right:
        mid = (left + right) // 2
        if check_distance(mid, L, N, K, supply_points):
            right = mid
        else:
            left = mid + 1
    return left

L, N, K = map(int, input().split())
supply_points = list(map(int, input().split()))
supply_points.sort()

answer = binary_search(L, N, K, supply_points)
print(answer)

以上代码中，check_distance函数用来判断给定的距离是否满足条件，binary_search函数用来进行二分搜索。最后，我们将得到的答案打印出来。

希望以上解答对您有帮助！如果还有任何问题，请随时提问。

跳转到最佳答案楼层

isdkz

二分答案是一种常用的算法技巧，可以用来解决一些满足某种性质的问题。对于这道题目，我们可以使用二分答案来确定新增的补给点使得相邻补给点间最大距离最小。

首先，我们可以观察到，相邻补给点间最大距离的取值范围是在0到L之间。我们可以将这个范围作为二分的上下界。

然后，我们需要编写一个函数来判断给定的距离是否满足条件。我们可以遍历原有的补给点，计算相邻补给点间的距离，如果有任意两个相邻补给点间的距离大于给定的距离，则说明当前的距离不满足条件。

接下来，我们可以使用二分搜索来找到满足条件的最小距离。我们设定二分搜索的初始上下界分别为0和L，然后进行循环，直到上下界相等。在每一次循环中，我们计算中间值mid，并调用判断函数判断mid是否满足条件。如果满足条件，说明我们可以继续缩小距离，将上界更新为mid；如果不满足条件，说明距离太小，需要增加距离，将下界更新为mid+1。

最后，当上下界相等时，说明我们找到了满足条件的最小距离，即为答案。

下面是具体的代码实现：

def check_distance(distance, L, N, K, supply_points):
    count = 0
    prev_point = 0
    for point in supply_points:
        count += (point - prev_point) // distance
        prev_point = point
    count += (L - prev_point) // distance
    return count >= N + K

def binary_search(L, N, K, supply_points):
    left = 0
    right = L
    while left < right:
        mid = (left + right) // 2
        if check_distance(mid, L, N, K, supply_points):
            right = mid
        else:
            left = mid + 1
    return left

L, N, K = map(int, input().split())
supply_points = list(map(int, input().split()))
supply_points.sort()

answer = binary_search(L, N, K, supply_points)
print(answer)

以上代码中，check_distance函数用来判断给定的距离是否满足条件，binary_search函数用来进行二分搜索。最后，我们将得到的答案打印出来。

希望以上解答对您有帮助！如果还有任何问题，请随时提问。

刘子诺

谢谢大佬！

刘子诺

isdkz 发表于 2023-11-8 20:58
二分答案是一种常用的算法技巧，可以用来解决一些满足某种性质的问题。对于这道题目，我们可以使用二分答案 ...

能不能用C++啊，然后测一下样例