USACO analysis
杨菲凡 |
19 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目
给出 $N$ 个范围，求出去掉一个范围后剩下范围覆盖的最大值
思路
用一个数组表示所有范围中的每个值出现的次数，遍历每个范围并求出去掉这个范围后剩下覆盖的值，再求最大值
复杂度分析
过程中一共需要遍历两次数组，总复杂度为 $O(n)$
代码
lines = open('lifeguards.in').read().strip().split('\n')
n = int(lines[0])
shifts = []
times = [0] * 1000
for i in range(1, n + 1):
line = tuple(map(int, lines[i].split(' ')))
shifts.append(line)
for j in range(line[0], line[1]):
times[j] += 1
#print(times)
max_count = 0
for shift in shifts:
count = 0
temp = times.copy()
for i in range(shift[0], shift[1]):
temp[i] -= 1
for i in temp:
if i > 0: count += 1
max_count = max(count, max_count)
print(max_count)
file = open('lifeguards.out', 'w')
file.write(str(max_count))
file.close()
