蓝桥杯真题代码记录(管道

简介: 蓝桥杯真题代码记录(管道

1. 题目:

有一根长度为 len 的横向的管道,该管道按照单位长度分为 len 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器

一开始管道是空的,位于 Li 的阀门会在 Si 时刻打开,并不断让水流入管道。


对于位于 Li 的阀门,它流入的水在 Ti (Ti ≥ Si) 时刻会使得从第 Li−(Ti−Si) 段到第 Li + (Ti − Si) 段的传感器检测到水流。 求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 n, len,用一个空格分隔,分别表示会打开的阀门数和管道长度。

接下来 n 行每行包含两个整数 Li , Si,用一个空格分隔,表示位于第 Li 段 管道中央的阀门会在 Si 时刻打开。

输出格式

输出一行包含一个整数表示答案。

样例输入

3 10

1 1

6 5

10 2

样例输出

5

2. 我的代码:

n, lenl = map(int, input().split())

LS = [] # 阀门和时刻

for _ in range(n):
    LS.append(list(map(int, input().split())))

# check
def check(t):
    harsh = [1] + [0] * lenl
    # 模拟水的流动
    for l, s in LS:
        for i in range(s, t + 1):
            try:
                harsh[l - (i - s)] = 1
            except:pass
            try:
                harsh[l + (i - s)] = 1
            except:pass

    if sum(harsh) >= lenl + 1:
        return True
    else:
        return False


# 二分法
left_p = 1
right_p = lenl

while left_p <= right_p:
    mid_p = (left_p + right_p) // 2
    a = check(mid_p - 1)
    b = check(mid_p)
    if a == False and b == True:
        break
    elif a == True:
        right_p = mid_p - 1
    elif b == False:
        left_p = mid_p + 1

print(mid_p)
目录
相关文章
|
30天前
|
网络安全 数据安全/隐私保护 计算机视觉
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
|
30天前
蓝桥杯真题代码记录(直线
蓝桥杯真题代码记录(直线
14 0
|
30天前
蓝桥杯真题代码记录(卡片
蓝桥杯真题代码记录(卡片
16 0
|
30天前
蓝桥杯真题代码记录(最优清零方案
蓝桥杯真题代码记录(最优清零方案
10 0
|
30天前
蓝桥杯真题代码记录(蜂巢
蓝桥杯真题代码记录(蜂巢
11 0
|
30天前
蓝桥杯真题代码记录(数位排序
蓝桥杯真题代码记录(数位排序
13 0
|
30天前
蓝桥杯真题代码记录(纸张尺寸
蓝桥杯真题代码记录(纸张尺寸
10 0
|
30天前
蓝桥杯真题代码记录(保险箱
蓝桥杯真题代码记录(保险箱
13 1
蓝桥杯真题代码记录(保险箱
|
30天前
|
索引
蓝桥杯真题代码记录(松散子序列
蓝桥杯真题代码记录(松散子序列
11 0
|
30天前
蓝桥杯vip测试题系统-数组求和(解题思路以及解题代码,手画思路图虽然丑丑的)
蓝桥杯vip测试题系统-数组求和(解题思路以及解题代码,手画思路图虽然丑丑的)
32 0