AcWing 4455. 出行计划
原题链接
简单
作者:
NFYD
,
2022-06-12 11:48:02
,
所有人可见
,
阅读 2720
- t时刻做核酸,可以在
[t + k, t + k + c - 1]
进入某个场所,其中c为进入场所时所需的单位时间数
- 若在ti时刻进入某场所,即要求
ti >= t + k
,且ti <= t + k + c - 1
,可以解得ti - k - c + 1 <= t <= ti - k
- 所以若在时刻q做了核酸,那么可以进入场所的区间为
[ti - k - c + 1, ti - k]
,即只需看时间q落在多少个区间内部,然后让这个区间内所有数加一即可,这可以利用差分来做。
- 对差分数组求前缀和数组即可得到原数组
差分 前缀和
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int n, m, k;
int d[N];
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i ++ )
{
int t, c;
scanf("%d%d", &t, &c);
d[max(1, t - k - c + 1)] ++ ;
d[max(1, t - k + 1)] -- ;
}
for(int i = 1; i <= N; i ++ )
{
d[i] += d[i - 1];
}
for(int i = 1; i <= m; i ++ )
{
int q;
scanf("%d", &q);
printf("%d\n", d[q]);
}
return 0;
}
为啥下标访问到N 不会报错呢
还有为啥i<N,N取2e+5呢博主
求解
比如做核酸时间t=1e5,出结果间隔k=1e5,生效时间就会变成t+k=2e5,访问下标t+k就越界了
博主,我想问问不进行条件判断就直接写d[]++吗,求解这个的原因
q<=t[i]-k&&q>=t[i]-k-c[i]+1,这个条件判断
tql
谢谢佬
右区间是
t - k
, 为什么代码里就变成了t - k + 1
?这里在
t-k+1
的后面(包括t-k+1
)核酸就过期了这是差分的模板,你可以看看算法基础课讲的
理解了,谢谢大佬orz
好的,谢谢大佬orz
谢谢佬
orz
明白了,感谢大佬 orz
orz 理解了,感谢大佬
tql
tql
tql
请问d【max】为什么要加加减减啊?
这个是差分数组,效果就是在区间的两个端点加上或减去一个数x,可以让整个区间内的所有数都加上或减去x,而不用一个一个遍历去加减。可以先了解一下差分。
https://oi-wiki.org/basic/prefix-sum/#%E5%B7%AE%E5%88%86
十分感谢
max那个是有什么用呀
差分数组下标从1开始,max保证下标最小为1,防止数组越界
OK 谢谢了