已过,一个问题
查看原帖
已过,一个问题
711859
ztksc07楼主2024/6/24 21:02

用差分进行区间修改,于是得到了这样一段代码:

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;
}

大概就是维护一个前缀和数组 bb 和一个差分数组 cfcf,每次清空差分数组和前缀和数组,用差分数组进行区间修改,用前缀和数组统计每一天所需教室数量,如果大于那一天的空闲教室数量就结束。

这段代码的提交记录是正确的。

然而我一开始忘了写前缀和数组 bb 的清空,提交记录依然是正确的。

请问这是什么原理,以及到底哪份代码是正确的。

2024/6/24 21:02
加载中...