题目描述

 解题思路

这个问题可以视为一个水波在管道中传播的问题，其中水波以单位速度传播。阀门在 S 时刻打开，水流以单位速度流向管道的右侧，每个传感器位于每段管道的中心。对于位于 Li 的阀门，在 Ti 时刻打开时，水波会在 Ti - S 时刻到达第 Li 段，并继续向右传播。

我们需要找到这样一个时刻，使得所有的传感器都检测到水流。由于水波是以单位速度传播的，我们可以按照阀门打开的时刻和水波传播的距离来计算每个传感器检测到水流的时刻。最早所有传感器都检测到水流的时刻，就是最后一个传感器检测到水流的时刻。

大佬题解

我觉得他这个代码思路非常清晰，而且跟我的思路一模一样，不过我写不出。

import os
import sys

# 请在此输入您的代码

# import time


def check(Ti, values, Len):
    """
    逐步缩小时间，寻找满足所有管道都能检测到水流时的最小时刻
    :param Ti:管道中每一段中间的传感器都能检测到有水流的时间
    :param values:最初打开的阀门与打开时刻点
    :param Len:管道长度
    :return:True or False
    """
    # 存储通过已打开的阀门，在Ti时刻能检测到水流的管道段
    section = []

    # 遍历每个已打开的阀门，计算并存入能检测到水流的管道段
    for Li, Si in values:
        if Ti >= Si:
            section.append((Li - (Ti - Si), Li + (Ti - Si)))

    # 将管道段按左边界升序排序
    section.sort()

    # 如果没有管道段或者第一个管道段的左边界大于1，即此Ti无法满足所有管道段都能检测到水流，上一个Ti为最小所求时间
    if not section or section[0][0] > 1:
        return False

    # 初始化最大右边界为第一个管道段的右边界
    right_boundary = section[0][1]

    # 遍历管道段，合并相邻的管道段
    for i in range(1, len(section)):
        if section[i][0] - right_boundary <= 1:  # 将管道段的左值与最大右边界比较
            right_boundary = max(right_boundary, section[i][1])  # 差值不大于1则更新最大右边界
        else:
            break

    # 如果最终的右边界大于等于管道长度，返回True，否则返回False
    return right_boundary >= Len


def main():
    # 输入已开启阀门数，管道总长度
    n, Len = map(int, input().split())
    # 输入阀门编号与开启时间
    values = [list(map(int, input().split())) for _ in range(n)]

    # start_time = time.perf_counter()

    # 初始化二分查找的左右边界
    left, right = 0, 10 ** 9

    # 二分查找
    while left < right:
        mid = (left + right) // 2
        if check(mid, values, Len):
            right = mid
        else:
            left = mid + 1

    # 输出结果
    print(left)

    # end_time = time.perf_counter()
    # print(f'用时{(end_time - start_time) * 1000}毫秒')


if __name__ == '__main__':
    main()

 我的解题过程

根据题目我画出了示意图，弄清楚题目中给出字母所代表的意思，根据题目中给出的输入数据和输出数据，我大致明白题目的意思，明白人应该怎么解题，但是在实现代码上能力还不太够。还是需要看大佬怎么写出代码的。

明白题目的意思和思路后解题其实不难，主要是写代码要多练和多运用。题目中用到二分查找，我知道二分查找的算法，但是不知道什么时候要运用这个算法，怎么运用。我再多练习练习，看我能不能自己写出来吧。

菜就多练！