T27104: 世界杯只因
greedy/dp, http://cs101.openjudge.cn/practice/27104/
卡塔尔世界杯正在火热进行中，P大富哥李哥听闻有一种叫"肤白·态美·宇宙无敌·世界杯·预测鸡"的鸡品种（以下简称为只因）有概率能准确预测世界杯赛果，一口气买来无数只只因，并把它们塞进了N个只因窝里，但只因窝实在太多了，李哥需要安装摄像头来观测里面的只因的预测行为。
具体来说，李哥的只因窝可以看作分布在一条直线上的N个点，编号为1到N。由于每个只因窝的结构不同，在编号为i的只因窝处安装摄像头，观测范围为a_i，其中a是长为N的整数列，表示若在此安装摄像头，可以观测到编号在 [ i - a_i , i + a_i ]（闭区间）内的所有只因窝。
李哥觉得摄像头成本高，决定抠门一下，请你来帮忙看看最少需要安装多少个摄像头，才能观测到全部N个只因窝。作为回报，他会请你喝一杯芋泥波波牛乳茶。
输入
第一行：一个正整数，代表有N个只因窝。 第二行给出数列a：N个非负整数，第i个数代表a_i，也就是在第i个只因窝装摄像头能观测到的区间的半径。
数据保证 N ≤ 500000，0 ≤ a_i ≤ N
输出
一个整数，即最少需要装的摄像头数量。
样例输入
10
2 0 1 1 0 3 1 0 2 0样例输出
3提示：彩蛋：只因们很喜欢那个穿着蓝白球衣长得像黄金矿工的10号
来源：计概A 2022期末
python
# 内存: 93420kB，时间: 905ms
import sys
input = sys.stdin.readline
n = int(input().strip())
a = list(map(int, input().split()))
intervals = []
for i in range(n):
L = max(1, (i+1) - a[i])
R = min(n, (i+1) + a[i])
intervals.append((L, R))
# 按左端升序排序
intervals.sort()
count = 0
cur_end = 0 # 当前已覆盖到的位置
i = 0
m = n
while cur_end < n:
# 在所有左端 <= cur_end+1 的区间中选取能把右端延伸最远的
best = cur_end
while i < m and intervals[i][0] <= cur_end + 1:
if intervals[i][1] > best:
best = intervals[i][1]
i += 1
count += 1
cur_end = best
print(count)python
# 计概B不A不C故没AC 224ms
def min_cameras_to_cover_all(ranges):
n = len(ranges)
ptr = 0
num = 0
mx = max(ranges)
while ptr < n:
# 假设下一个指针位置为当前指针加上当前观测范围再加一
nxt = ptr + ranges[ptr] + 1
# 遍历一个以当前指针为中心的大窗口，考虑到最大观测范围mx的影响
for i in range(max(0, ptr - mx), min(n, ptr + mx + 1)):
if 0 <= i < n and i - ranges[i] <= ptr and i + ranges[i] + 1 > nxt:
nxt = i + ranges[i] + 1 # 更新最远可达位置
num += 1 # 每次循环代表安装了一个摄像头
ptr = nxt # 移动到最远可达位置继续搜索
return num
# 输入处理
if __name__ == "__main__":
_ = int(input()) # 忽略第一行的N值
ranges = list(map(int, input().strip().split()))
print(min_cameras_to_cover_all(ranges))python
# 数院胡睿诚 660ms
# 1）按照区间左端点从小到大排序。
# 2）从前往后依次枚举每个区间，在所有能覆盖当前目标区间起始位置start的区间之中，
# 选择右端点最大的区间。
# 假设右端点最大的区间是第 i 个区间，右端点为 ri；
# 最后将目标区间的start更新成 ri + 1。
def calculate_min_coverage(n, points):
clips = [(max(0, i-point), min(n-1, i+point))
for i, point in enumerate(points)]
clips.sort()
st, ed = 0, n-1
res = 0
current_index = 0
while current_index < n:
maxR = -float("inf")
while current_index < n and clips[current_index][0] <= st:
maxR = max(maxR, clips[current_index][1])
current_index += 1
if maxR < st:
break
res += 1
if maxR >= ed:
break
st = maxR + 1
return res
N = int(input())
points = list(map(int, input().split()))
print(calculate_min_coverage(N, points))python
def calculate_min_coverage(n, points): # 831ms
# 将每个点的可覆盖范围转化为区间 [max(0, i - points[i]), min(n, i + points[i] + 1))
clips = [(max(0, i - points[i]), min(n, i + points[i] + 1)) for i in range(n)]
clips.sort() # 按区间左端点从小到大排序
st, ed = 0, n # st: 当前目标起始位置, ed: 结束位置是n（全覆盖范围）
res = 0 # 记录安装摄像头的数量
current_index = 0 # 当前枚举到的区间索引
while st < ed:
maxR = -1 # 当前轮次中能覆盖的最远右端点
# 遍历所有左端点 <= st 的区间，并找到覆盖范围最远的区间
while current_index < n and clips[current_index][0] <= st:
maxR = max(maxR, clips[current_index][1])
current_index += 1
# 如果无法推进覆盖范围，说明无法覆盖目标区域，返回 -1
if maxR <= st:
return -1
res += 1 # 安装一个摄像头
st = maxR # 更新目标区间的起始位置
# 如果当前区间的右端点已经覆盖到ed，结束循环
if st >= ed:
break
return res
# 输入与输出处理
if __name__ == "__main__":
N = int(input())
points = list(map(int, input().split()))
print(calculate_min_coverage(N, points))修正与优化内容
- 修复覆盖范围计算：
- 原代码
min(n-1, i+point)的右端点不准确，应为min(n, i + point + 1)。- 因为
i + point是闭区间的最远点，但我们需要将其扩展到 右开区间min(n, i + point + 1)才能确保边界覆盖完整。- 终止条件调整：
- 原代码中，
ed被赋值为n-1，但实际上目标是覆盖[0, n)，因此ed应为n。- 无法推进的判断：
- 在循环中，如果
maxR <= st，说明当前无法覆盖目标区域的起点，立即返回-1。- 边界简化：
- 避免混乱地使用
break和多个终止条件，确保逻辑清晰，使用st >= ed作为主要终止条件。代码核心思路
- 排序区间： 按照区间的左端点从小到大排序。
- 贪心选择右端点： 对于所有能覆盖当前目标位置
st的区间，选择右端点最大的区间。- 更新目标位置： 每次选择完区间后，将目标位置
st更新为当前区间的右端点。- 终止条件：
- 如果当前目标位置
st已经覆盖到n，说明所有位置都被覆盖。- 如果无法找到一个区间推进覆盖范围，返回
-1。复杂度分析
- 时间复杂度：O(NlogN)O(N \log N)O(NlogN)
- 排序区间的复杂度为 O(NlogN)O(N \log N)O(NlogN)。
- 遍历区间的复杂度为 O(N)O(N)O(N)。
- 空间复杂度：O(N)O(N)O(N)
- 存储区间需要 O(N)O(N)O(N) 空间。
如果做了数据预处理，相当于用了字典/桶，减少了数据，也自然排了序。所以时间会缩小。后面程序都不用动。
python
# 数院胡睿诚
# 1）按照区间左端点从小到大排序。
# 2）从前往后依次枚举每个区间，在所有能覆盖当前目标区间起始位置start的区间之中，
# 选择右端点最大的区间。
# 假设右端点最大的区间是第 i 个区间，右端点为 ri；
# 最后将目标区间的start更新成 ri + 1。
def calculate_min_coverage(n, points):
#clips = [(max(0, i-point), min(n-1, i+point))
# for i, point in enumerate(points)]
# 数据预处理，计算每个起点的最远结束点。
ends = [0]*n
for i in range(n):
left_index = max(i - points[i], 0)
ends[left_index] = max(ends[left_index], i + points[i])
clips = [(i, ends[i]) for i in range(n)]
#clips.sort()
st, ed = 0, n-1
res = 0
current_index = 0
while current_index < n:
maxR = -float("inf")
while current_index < n and clips[current_index][0] <= st:
maxR = max(maxR, clips[current_index][1])
current_index += 1
if maxR < st:
break
res += 1
if maxR >= ed:
break
st = maxR + 1
return res
N = int(input())
points = list(map(int, input().split()))
print(calculate_min_coverage(N, points))python
# 数院胡睿诚 time: 897ms
# 就是从左往右扫，一轮一轮的扫
# 比如现在这一轮结束之后第一个没被盖住的是x,你就继续扫能盖住x的，
# 在所有能盖住x的里面挑右端点最靠右边的，把它选进来，然后更新第一个没被盖住的点，进入下一轮
#
# 其实这个算法对于任给一族区间要找最小覆盖的问题都对
N = int(input())
a = list(map(int, input().split()))
intervals = [(max(0, i-a[i]), min(N-1, i+a[i])) for i in range(N)]
intervals.sort()
ans = 0
right = 0
temp = -1
index = 0
while index < N and right < N:
while index < N and intervals[index][0] <= right:
temp = max(temp, intervals[index][1])
index += 1
right = temp + 1
ans += 1
print(ans)gpt优化
python
# 胡睿诚
# 区间覆盖问题的解法，它的目的是为了找到最小数量的区间，使整个给定范围都被这些区间覆盖。
def min_interval_cover(N, points):
# 创建区间并按照左端点排序
intervals = [(max(0, i-point), min(N-1, i+point)) for i, point in enumerate(points)]
intervals.sort()
# 最小覆盖区间数量
cover_count = 0
# 当前未被覆盖的最右位置
uncovered = 0
# 能覆盖当前最右位置的最远右端点
max_right = -1
# 当前区间的索引
current_index = 0
while current_index < N and uncovered < N:
# 寻找能覆盖uncovered位置的区间，更新最远右端点
while current_index < N and intervals[current_index][0] <= uncovered:
max_right = max(max_right, intervals[current_index][1])
current_index += 1
# 更新未被覆盖的位置
uncovered = max_right + 1
# 增加区间数量
cover_count += 1
return cover_count
N = int(input())
points = list(map(int, input().split()))
print(min_interval_cover(N, points))桶排序
python
#夏天明2300017735; time: 537ms
#罗景轩2300012610
n = int(input())
a = list(map(int, input().split()))
ends = [0]*n
for i in range(n):
ends[max(i - a[i], 0)] = max(ends[max(i - a[i], 0)], i + a[i] + 1)
l, r = -1, 0
ans = 0
while r < n:
l, r = r, max(ends[l + 1: r + 1])
ans += 1
print(ans)Gpt优化
python
# 夏天明2300017735; 罗景轩2300012610
# 贪心算法来求解区间覆盖问题
def calculate_min_coverage(n, intervals):
# 计算每个起点的最远结束点。
ends = [0]*n
for i in range(n):
left_index = max(i - intervals[i], 0)
ends[left_index] = max(ends[left_index], i + intervals[i] + 1)
# 初始化左边和右边的边界指针以及区间计数器。
left_boundary, right_boundary = -1, 0
cover_count = 0
# 用贪心算法寻找最少的区间覆盖完全部点。
#while right_boundary < n:
# 获取当前最大覆盖范围。
# new_right_boundary = max(ends[left_boundary + 1: right_boundary + 1])
# 优化：跟踪当前的最大值，而不是对列表进行切片
current_max = 0
while right_boundary < n:
# 只在必要时扫描ends数组，确定新的右边界。
if right_boundary >= current_max:
for i in range(left_boundary + 1, right_boundary + 1):
current_max = max(current_max, ends[i])
new_right_boundary = current_max
# 更新左边界和右边界。
left_boundary, right_boundary = right_boundary, new_right_boundary
# 更新覆盖区间计数。
cover_count += 1
return cover_count
n = int(input())
intervals = list(map(int, input().split()))
print(calculate_min_coverage(n, intervals))苏王捷思路：用最小堆实现对监视范围最左端从小到大的排序，然后依次取出，找到能接上前一段并且最右端最远的监视范围，ans+1，继续直到最右端=n
python
# 苏王捷 time: 2049ms
# 用最小堆实现对监视范围最左端从小到大的排序，然后依次取出，
# 找到能接上前一段并且最右端最远的监视范围，ans+1，继续直到最右端=n
import heapq
n=int(input())
l=[0]+list(map(int,input().split()))
queue=[]
for i in range(1,n+1):
heapq.heappush(queue,[max(1,i-l[i]),min(i+l[i],n)])
right=ans=0
while right<n:
tmpright=right
camera=heapq.heappop(queue)
while camera[0]<=right+1:
if camera[1]>tmpright:
tmpright=camera[1]
if tmpright==n:
break
if queue:
camera=heapq.heappop(queue)
else:
break
heapq.heappush(queue,camera)
if tmpright!=right:
ans+=1
right=tmpright
print(ans)