CCF CSP 202203-2 出行计划

C++未优化版【70分】【从人的角度考虑问题】

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
struct plan{int t;int c;
}P[100000+1];
int main(){int n,m,k;cin>>n>>m>>k; for(int i=1;i<=n;i++){int t,c;cin>>t>>c;P[i].t = t;P[i].c = c;}while(m--){int q;cin>>q;int count = 0;//从人的角度，每做一次核酸，就查询进入场所的时间t是否在核酸检测结果出来[q+k]后，c小时内 for(int i=1;i<=n;i++){if(q+k<=P[i].t && P[i].t<=(q+k+P[i].c-1))count++;}cout<<count<<endl;}
}

C++优化版

基于未优化版本，考虑将n个出行计划的查询（即内层for循环）放到外层循环之外。对于每个查询（即每个核酸检测），获得核酸检测结果的时间点，求出其被多少个出行计划所覆盖。问题变为：在O(n)时间内，求出每个查询获得的核酸结果时间点被多少个出行计划所覆盖。

如果一个场所要求持 24 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 t+k 时刻到第 t+k+23 时刻进入该场所。

由题目中上段文字的描述可知，如果某出行计划要在t时刻进入场所，获得核酸检测结果的时间点应该在[t-c+1,t]内（上段文字中c值为24），核酸检测结果才能生效。由于获得核酸检测结果的时刻>=1（因为等待核酸检测结果的时间k>0，所以获得核酸检测结果的时刻总是>=1），因此上述区间可以改为[max(1,t-c+1),t]。且针对n个出行计划的输入，都能对应一个上述区间。如下：

5 24--->[1,5]
10 24--->[1,10]
11 24--->[1,11]
34 24--->[11,34]
35 24--->[12,35]
35 48--->[1,35]

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 4e5+5;
int main(){int n,m,k;int b[N];cin>>n>>m>>k; int t,c;for(int i=1;i<=n;i++){cin>>t>>c;int left = t-c+1;left = left>0?left:1;int right = t;b[left]++; //差分数组b[left]++ b[right+1]--;//差分数组b[right+1]-- }//差分数组b的前缀和数组 for(int i=1;i<=N;i++){b[i] = b[i]+b[i-1];}while(m--){int q;cin>>q;cout<<b[q+k]<<endl;}return 0;
}