CCF-CSP真题《202203-2—出行计划》思路+python满分题解

骑猪看日落 2023-09-29 15:21 27阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202203-2</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>出行计划</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.5s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题描述</h3> <p>最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。</p> <p>具体来时，如果在&nbsp;t&nbsp;时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要&nbsp;k&nbsp;个单位时间，即在&nbsp;t+k&nbsp;时刻可以获得结果。如果一个场所要求持&nbsp;24&nbsp;个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第&nbsp;t+k&nbsp;时刻到第&nbsp;t+k+23&nbsp;时刻进入该场所。</p> <p>小 C 按时间顺序列出接下来的&nbsp;n&nbsp;项出行计划，其中第&nbsp;i&nbsp;项（1≤i≤n）可以概括为：<br> ti&nbsp;时刻进入某场所，该场所需持有&nbsp;ci&nbsp;个单位时间内的核酸检测结果入内，其中&nbsp;0&lt;ci≤2×105。</p> <p>为了合理安排核酸检测时间，试根据小 C 的出行计划，回答如下查询：</p> 
    <ul> 
     <li>如果在&nbsp;q&nbsp;时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？</li> 
    </ul><p>这样的查询共有&nbsp;m&nbsp;个，分别为&nbsp;q1,q2,⋯,qm；查询之间互不影响。</p> <h3>输入格式</h3> <p>输入的第一行包含空格分隔的三个正整数&nbsp;n、m&nbsp;和&nbsp;k，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。</p> <p>接下来输入&nbsp;n&nbsp;行，其中每行包含用空格分隔的两个正整数&nbsp;ti、ci，表示一项出行计划；出行计划按时间顺序给出，满足&nbsp;0&lt;t1≤t2≤⋯≤tn≤2×105。</p> <p>最后输入&nbsp;m&nbsp;行，每行仅包含一个正整数&nbsp;qi，表示一个查询。m&nbsp;个查询亦按照时间顺序给出，满足&nbsp;0&lt;q1&lt;q2&lt;⋯&lt;qm≤2×105。</p> <h3>输出格式</h3> <p>输出共&nbsp;m&nbsp;行，每行一个整数，表示对应查询的答案。</p> <h3>样例输入</h3> 
    <blockquote> 
     <p>6 2 10<br> 5 24<br> 10 24<br> 11 24<br> 34 24<br> 35 24<br> 35 48<br> 1<br> 2</p> 
    </blockquote> <h3>样例输出</h3> 
    <blockquote> 
     <p>3<br> 3</p> 
    </blockquote> <h3>样例解释</h3> <p>时刻&nbsp;1&nbsp;做检测，可以满足第三、四、六项出行计划；</p> <p>时刻&nbsp;2&nbsp;做检测，可以满足第四、五、六项出行计划。</p> <h3>子任务</h3> <p>40%&nbsp;的测试数据满足&nbsp;0&lt;n,k≤1000、m=1；</p> <p>70%&nbsp;的测试数据满足&nbsp;0&lt;n,m,k≤1000；</p> <p>全部的测试数据满足&nbsp;0&lt;n,m,k≤105。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[出行计划][Link 1]

> 感兴趣的同学可以进去进行练习提交

**70分题解：**

n, m, k = map(int,input().split())
    spots = [[i for i in map(int, input().split())] for j in range(n)]
    times = []
    for i in range(m):
        point = int(input())
        times.append(point+k)
    for time in times:
        num = 0
        temp = sorted(spots,key = lambda x:(x[1]-time-x[0]),reverse = True)
        for spot in temp:
            if spot[0] < time:
                continue
            if time <= spot[0] < time+spot[1]:
                num += 1      
            if spot[0] >= time+spot[1]:
                break 
        print(num)

**解题思路：**

> 70分代码的思路我们是站在人（小C）的角度处理问题，即按照他的思路（即题目要求）一步一步处理问题，优先解决人的需求；
> 
> 在代码中，运行时间过长的原因在于双重循环；  
> 仔细思考后发现：在外层循环中，time是按照时间顺序给出，则存在重复判断的情况，例如，无论time=11还是time=12，第五组数据35 24都不符合要求，但是在70分程序中该情况盘端了两次，导致重复;我们接下来只需要将这部分重复判断的操作去除，将两层循环改成一层循环即可；

**运行结果：**

![be95bcf72f244770a5f60038fe76b5d5.png][]

--------------------

**满分题解：**

n, m, k = map(int,input().split())
    spots = [[i for i in map(int, input().split())] for j in range(n)]
    num = 0
    for i in range(n):
        if num < spots[i][0]:
            num = spots[i][0]+1
        spots[i][0], spots[i][1] = max(1,spots[i][0]-spots[i][1]+1), spots[i][0]
    times = []
    for i in range(m):
        point = int(input())
        times.append(point+k)
    temp = [0 for i in range(num*2)]
    for spot in spots:
        temp[spot[0]] += 1
        temp[spot[1]+1] -= 1
    for i in range(1,num+1):
        temp[i] += temp[i-1]
    for time in times:
        print(temp[time])

**解题思路：**

> 在满分的解题思路中，我们优先处理场所需求，即判断出进入该场所需要的最早时间核酸报告和最晚时间核酸报告；然后再考虑人的需求，即人在核酸适合进场这个时间范围内进入场所都是符合要求的，可将问题转化为对区间的处理：核酸检测的时间t+等待核酸检测的时间k所在的点有多少个满足条件的场所；  
> 此100分代码考虑差分算法，差分数组适合于多次区间修改，极少区间查询或者先区间修改再区间查询，不是边修改边查询的情况。本题使用差分数组，每个出行计划就是对有效区间的操作。最后前缀和统计一下，随后查询即可。

**运行结果：**

![671828201aa140f9b82c90a56986921d.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T142
[be95bcf72f244770a5f60038fe76b5d5.png]: https://img-blog.csdnimg.cn/be95bcf72f244770a5f60038fe76b5d5.png
[671828201aa140f9b82c90a56986921d.png]: https://img-blog.csdnimg.cn/671828201aa140f9b82c90a56986921d.png