解题思路:
1、对时间进行二分搜索,
2、对于每个判断的时间,可以每个阀门视为一个区间,判断由此得到区间组是否能够覆盖整个大区间
注意事项:
1、右边界需要开大一点,10的9次方不行,需要开到10的10次方
2、得到的区间一定要先排序(阀门开的时间不同,可能会出现区间交错,包含的情况)
参考代码:
def check(t): ls = [] for i, (x, y) in enumerate(vle): if t >= y: ls.append((x-(t-y),x+(t-y))) # 将阀门展开为区间 ls.sort() if len(ls) == 0: return False if ls[0][0] > 1: return False r = ls[0][1] for i in range(1, len(ls)): # 判断是否能够覆盖区间 if ls[i][0]-r <= 1: r = max(r, ls[i][1]) else: break return r >= lon n, lon = map(int, input().split()) vle = [] for i in range(n): vle.append(list(map(int, input().split()))) l, r = 0, 10**10 while l < r: # 二分搜索时间,右边界需要开大一些 mid = (l+r)//2 if check(mid): r = mid else: l = mid+1 print(l)
0.0分
7 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:470 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:553 |
大家好,我是验题君浏览:577 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:486 |
GC的苦恼 (C语言代码)浏览:620 |
分糖果 (C语言代码)浏览:913 |
C语言程序设计教程(第三版)课后习题12.3 (C语言代码)浏览:543 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:585 |
A+B for Input-Output Practice (II) (C语言代码)浏览:600 |
10月月赛题解浏览:536 |
我是熊2 2024-02-25 17:07:01 |
如果你大于1说明你没有把第一个管道覆盖到