用差分进行区间修改,于是得到了这样一段代码:
bool borr(int mid){
memset(cf,0,sizeof(cf));
memset(b,0,sizeof(b));
for(int i=1;i<=mid;i++){
cf[s[i]]+=d[i];
cf[t[i]+1]-=d[i];
}
for(int i=1;i<=n;i++){
b[i]=b[i-1]+cf[i];
if(b[i]>r[i]) return 0;
}
return 1;
}
大概就是维护一个前缀和数组 b 和一个差分数组 cf,每次清空差分数组和前缀和数组,用差分数组进行区间修改,用前缀和数组统计每一天所需教室数量,如果大于那一天的空闲教室数量就结束。
这段代码的提交记录是正确的。
然而我一开始忘了写前缀和数组 b 的清空,提交记录依然是正确的。
请问这是什么原理,以及到底哪份代码是正确的。