CCF CSP——202203-2 出行计划

问题描述

试题链接：出行计划

满分题解

此题为一般简单模拟题，题目读完，这不就是遍历一遍所有场所，根据场所需要的c个小时核酸，那么判断计划的t'是否属于[t+k, t+k+c)的范围，是则answer加一，最后输出answer，三下五除二写完，啪，提交，结果70分超时。。。

因为之前做这道题的时候是记时间做的，70分感觉也还行，当时也没有更好的优化方法，直接就做下一题了。

后面回过头来想这道题的时候，发现了可以优化时间的方法，之前的做法对于只有一个输入的时候确实很好使，但是对于输入较多的时候，每一次都需要遍历一遍所有的场所，对于同一组数据，每次输入对应的结果都是不会变化的，因此考虑以空间的代价，换时间，直接将所有可能的输入的答案全部保存下来，随后对于每个输入，只需要O(1)的时间复杂度即可获得答案。

具体实现细节如下代码

python代码

n, m, k = map(int, input().split())
max_time = 0
activities = []
for i in range(n):
    activity = list(map(int, input().split()))
    activity[0], activity[1] = max(0, activity[0] - activity[1] + 1 - k), activity[0] - k
    if activity[1] < 0:
        continue
    max_time = max(max_time, activity[1] + 2)
    activities.append(activity)

ans = [0] * max_time
for activity in activities:
    ans[activity[0]] += 1
    ans[activity[1] + 1] -= 1
for i in range(1, max_time):
    ans[i] += ans[i - 1]
for i in range(m):
    inp = int(input())
    print(ans[inp] if inp < max_time else 0)

写在最后

 祝大家CSP认证都400+

 祝大家CSP认证都400+

 祝大家CSP认证都400+