CSP 202203-2 出行计划 python 差分算法
题目描述
思路
这道题实际上是利用差分进行计算，也就是进行区间修改
我们可以大概找一下思路，首先我们的数据来说，我们能够正常进行计划的做核酸的时间是
我们可以看到，只要满足这个条件，我们就可以完成我们计划，所以我们需要对这个区间的值都进行+1的操作，对于差分数组来说，我们就只需要对两端进行操作，也就是t [ l ] + = 1 ,
我们还可以对这个公式进行一个转化
所以我们只需要得到我们的q在这个 [t-l-c+1,t-k]上的值，就是我们的计划的数。
之后对差分数组求和，就可以得到计划的数，计算这里面的值，最后的diff[q]就是我们的结果。
代码
# http://118.190.20.162/view.page?gpid=T142 n,m,k = map(int,input().split()) N = 200010 diff = [0]*N for i in range(n): t,c = map(int,input().split()) # 在【l, r】时间段内做核酸，则t时刻可进入 l = max(t-k-c+1,0) r = max(t-k,0) # 在【l, r】时间段内能出行的计划个数加一 diff[l] += 1 diff[r+1] -= 1 # 利用差分计算每个时间的能出行个数 for i in range(1,N): diff[i] += diff[i-1] for j in range(m): q = int(input()) res = diff[q] print(res)
