目录
一、题目
二、解题报告
三、知识风暴
一、题目
1、原题链接
2、题目描述
如果在 q 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？
6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2
3
3
二、解题报告
1、思路分析
我的思路
1）按照题意进行模拟，依次计算可以满足条件的答案数。
2）依次输出答案，即为所求。
（TLE，只通过了70%的数据）
y总思路
1）开一个数组代表在各个时刻q时，满足的计划数有多少个。
2）从暴力解法思想中用来判断是否是满足核酸检测要求的计划的条件中可以解得q的范围t[i]-c[i]-k+1<=q<=t[i]-k，代表针对每个计划i，在该时间段区间中都可以进入，所以更新对应数组元素的值，代表该时刻满足的核酸检测的计划数+1，直至统计完所有的计划。
3）针对上述过程，对某一给定区间加1，可以利用差分来进行操作。
4）模拟上述过程，输出结果即为所求。
2、时间复杂度
我的思路时间复杂度为O(n^2)
y总思路时间复杂度为O(n)
3、代码详解
我的思路的代码
#include
using namespace std;
int t[100010],c[100010],ans[100010];
int main()
{ int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<n;i++){
cin>>t[i]>>c[i];
}
int q;
for(int i=0;i<m;i++){
cin>>q;
for(int j=0;j<n;j++){
if(q+k<=t[j]&&q+k+c[j]-1>=t[j]){
ans[i];
}
}
}
for(int i=0;i<m;i){
cout<<ans[i]<<endl;
}
return 0;
}
y总思路的代码
#include
using namespace std;
int d[200010];
int ans[10010];
int main()
{ int n,m,k;
cin>>n>>m>>k;
int t,c;
for(int i=0;i<n;i++){
cin>>t>>c;
int l=t-c-k+1;
int r=t-k;
//差分
//区间右端点大于0才有合法
if(r>0){
d[max(1,l)]; //在区间右端点合法时，左端点最小为1，因为查询的时刻q大于0，所以当左端点不合法时，也需要保证左端点在有效范围内
d[r+1]–;
}
}
int q;
//前缀和
for(int i=1;i<200010;i){
d[i]+=d[i-1];
}
for(int i=0;i<m;i++){
cin>>q;
cout<<d[q]<<endl;
}
return 0;
}
三、知识风暴
差分与前缀和
