202203-2 出行计划 （Python 附思路）_出行计划 csdn

题目要求：

70分代码：

# 70分
n,m,k = map(int, input().split())    # 接收n、m、k三个输入
t = []
c = []
q = []
 
# 接收n个出行计划 ti、ci
for i in range(n):    
    ti,ci = map(int, input().split())
    t.append(ti), c.append(ci)
 
# 从用户视角出发，计算每个查询对应能去的出行计划有几个
def num(start):    
    count = 0
    for i in range(n):
        if start <= t[i] and t[i]-start < c[i]:
            count += 1
    return count 
 
# 接收m个查询
for i in range(m):    
    value = int(input())
    q.append(value)
 
# 这样时间复杂度是m×n 会超时
for i in range(m):
    print(num(q[i]+k))

满分思路及代码：

跳出传统惯性思维，不从用户角度去逐一计算每个查询能满足多少个出行计划，而是先从出行计划入手，计算对于每个出行计划所满足的q时刻做疫苗时间段：

由题意易知有：

即：

变换后得：

此时只需要开辟一个大小为200010（注意一定要开多几个，避免越界）的数组q，用于记录对于该出行计划，哪些q时刻是可行的，对这些可行的q都+1，因此这里可以用到差分的思想：

代码

# 100分
n,m,k = map(int, input().split())
t = []
c = []
 
res = [0]*200010    # 要多开几个防止越界
 
for i in range(n):
    ti,ci = map(int, input().split())
    t.append(ti), c.append(ci)
 
#------------------差分核心部分------------------#
 
    l = max(t[i]-c[i]-k+1,0)
    r = max(t[i]-k,0)
    res[l] += 1
    res[r+1] -= 1
 
for i in range(1,len(res)):    
    res[i] += res[i-1]    # 前缀和累加
 
#-----------------------------------------------#
 
for i in range(m):
    value = int(input())
    print(res[value])