2022-08-09 • 竞赛专题

CSP-202203-2

出行计划-题目描述

最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。

具体来时，如果在 t 时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要 k 个单位时间，即在 t+k 时刻可以获得结果。如果一个场所要求持 24 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 t+k 时刻到第 t+k+23 时刻进入该场所。

小 C 按时间顺序列出接下来的 n 项出行计划，其中第 i 项（1≤i≤n）可以概括为：
ti 时刻进入某场所，该场所需持有 ci 个单位时间内的核酸检测结果入内，其中 0<ci≤2×105。

为了合理安排核酸检测时间，试根据小 C 的出行计划，回答如下查询：

如果在 q 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？

这样的查询共有 m 个，分别为 q1,q2,⋯,qm；查询之间互不影响。

输入格式

输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。

接下来输入 n 行，其中每行包含用空格分隔的两个正整数 ti、ci，表示一项出行计划；出行计划按时间顺序给出，满足 0<t1≤t2≤⋯≤tn≤2×105。

最后输入 m 行，每行仅包含一个正整数 qi，表示一个查询。m 个查询亦按照时间顺序给出，满足 0<q1<q2<⋯<qm≤2×105。

输出格式

输出共 m 行，每行一个整数，表示对应查询的答案。

输入

输出

3
3

说明/提示

样例解释

时刻 1 做检测，可以满足第三、四、六项出行计划；

时刻 2 做检测，可以满足第四、五、六项出行计划。

子任务

40% 的测试数据满足 0<n,k≤1000、m=1；

70% 的测试数据满足 0<n,m,k≤1000；

全部的测试数据满足 0<n,m,k≤105。。

思路解析

对于每一个位于ti,有效期为ci的计划，都用mark数组进行标记。

如果在mark[ti-ci] ~ mark[ti]区间内查询则有效

也就是time + k在此区间内

但是，ti-ci可能是小于0的

这样的话，赋值其为0就可以，因为负数的time值并不存在。

所以现在问题变成了：

有若干个区间和若干次查找，求每次查找有多少符合要求的区间。

所以差分+前缀和

每次输入线段信息时，左侧端点赋值1，右侧端点赋值-1

信息输入结束后，从头到尾遍历一遍数组，进行前缀和的叠加

其实，这个正确答案就是[错误代码-2 70分]的优化版本而已

输入输出部分

#老规矩，先考虑输入输出
n, m, k = map(int,input().split())
ls = list([0] * 500000)[::]
#用一个列表来存储线段信息，使得每次查询ls[i]就是i时刻的答案
#由于输出是即时的，就不在这部分写了

核心代码

for i in range(n):
    ti, ci = map(int,input().split())#处理数据
    if ti-ci > 0:#左端点大于0的话，进行左端点的赋值
        ls[ti - ci + 1] += 1
    else:#由于时间没有负数，左端点小于0的话，进行ls[0]的赋值
        ls[0] += 1
    ls[ti + 1] -= 1#右端点赋值
#差分结束

#求前缀和
for i in range(1,500000):
    ls[i] += ls[i-1]

#查找
for i in range(m):
    time = int(input())
    print(ls[time + k])

汇总代码

n, m, k = map(int,input().split())
ls = list([0] * 500000)[::]
for i in range(n):
    ti, ci = map(int,input().split())
    if ti-ci > 0:
        ls[ti - ci + 1] += 1
    else:
        ls[0] += 1
    ls[ti + 1] -= 1

for i in range(1,500000):
    ls[i] += ls[i-1]

for i in range(m):
    time = int(input())
    print(ls[time + k])

评测链接

【CSP 202203-2】首页 - 计算机软件能力认证考试系统

错误代码-1 70分

#暴力模拟版

#查找函数
def query(time):
    global ls, k
    ans = 0
    for tmp in ls:
        if time + k <= tmp[0] <= time + k + tmp[1] - 1:
            ans += 1
    return ans

#代码
n, m, k = map(int,input().split())
ls = []
for i in range(n):
    ti, ci = map(int,input().split())
    ls.append([ti, ci])
for i in range(m):
    time = int(input())
    print(query(time))

错误代码-2 70分

#没有用到前缀和的线段查找版本

#输入
n, m, k = map(int,input().split())
ls = list([0] * 500000)[::]
for i in range(n):
    ti, ci = map(int,input().split())
    for j in range(ti - ci + 1, ti + 1):#ci时刻的计划，要求ci内的时间
        ls[j] += 1						#和正确答案唯一的区别，就是存入线段数据时耗时太长了
        								#正确答案用前缀和，一遍O(n)，这里是O(n^2)
for i in range(m):
    time = int(input())
    print(ls[time + k])					#一样的查找

风几许的编程小站