CCF-CSP 202203-2 出行计划 差分算法满分题解+解题思路

题目链接：202203-2 出行计划

70分思路：

按照题目要求，直接设置两个数组，记录进入场所的时刻t和单位时间c，即int t[N],c[N];由于需要知道核酸检测结果出来的时刻，则直接设置为l，即int l = q+k;双重循环进行判断，外循环为输入q，内循环遍历数组进入场所的时刻t必须满足：已出检测结果+检测结果未过期

70分具体代码如下：

#include <iostream> #include <algorithm> using namespace std; const int N = 1e5+10;//数据范围 int n,m,k;//输入 int t[N],c[N];//记录t时刻，c单位时间 int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) { cin>>t[i]>>c[i]; } for(int i=1;i<=m;i++) { int sum = 0;//用于输出 int q; cin>>q; int l = q+k;//定义时间的左边界，即检测结果出来的时刻 for(int j=1;j<=n;j++) { if(l<=t[j]&&l+c[j]-1>=t[j])//进入场所的时刻t必须满足：已出检测结果+检测结果未过期 { sum++; } } cout<<sum<<endl; } return 0; }

100分思路：

由70分代码可知，运行时间过长的原因在于双重循环仔细思考后发现：在外层循环中，qi是按照时间顺序给出，则存在重复判断的情况，例如，无论q=1还是q=2，第一组数据5 24都不符合要求，但是在70分程序中该情况盘端了两次，导致重复我们接下来只需要将这部分重复判断的操作去除，将两层循环改成一层循环即可70分代码的思路我们是站在人（小C）的角度处理问题，即按照他的思路（即题目要求）一步一步处理问题，优先解决人的需求；接下来100分代码思路中，我们优先处理场所需求，即判断出进入该场所需要的最早时间核酸报告（left）和最晚时间核酸报告（right）后考虑人的需求，即人在left～right这个时间范围内进入场所都是符合要求的，可将问题转化为对区间的处理：核酸检测的时间t+等待核酸检测的时间k所在的点有多少个满足条件的场所此100分代码考虑差分算法，便于在left～right之间加上一个数，时间复杂度为O(n)注意数组的大小开成4e5+10,因为会考虑到t+q即最大为2e5+2e5

100分具体代码如下：

#include<iostream> #include<algorithm> using namespace std; const int N = 4e5+10; int n,m,k; int b[N];//差分数组 //令l～r之间的数都+c void insert(int l,int r,int c) { b[l]+=c; b[r+1]-=c; } int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; int left = x-y+1;//定义左边界 left = left>0?left:1; int right = x;//定义右边界 insert(left,right,1); } //前缀和操作，得到各个点的数值 for(int i=1;i<=N;i++) { b[i] = b[i-1]+b[i]; } while(m--) { int x; cin>>x; cout<<b[x+k]<<endl;//直接得到x+k处的数值 } return 0; }

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。