Peter算法小课堂—差分数组

我们先看一道例题：

太戈编程第1590题

1590. 修正带2

题目描述

小明写作文时，每次写错一句就马上会用修正带涂一次错误的地方。已知他作业最终共写了n个字，写作过程中错了m次，第i次错误是从第a[i]个字错到第b[i]个字，于是他将这些字涂上一层修正带。小明的错误罄竹难书，写着写着他发现有些地方的修正带变得越来越厚，小明想知道最厚的地方有几层修正带？

暴力模拟法

假设s[i]代表j号字被涂了几层

for(int i=1;i<=m;i++){
	cin>>a>>b;
	for(int j=a;j<=b;j++) s[j]++;
}

时间复杂度：O(nm)    我们可以换一种方法去进行一个优化，这个方法叫做传说中的“差分数组”

差分数组法

给定原数组s[]，对应差分数组d[]

d[i]=s[i]-s[i-1],i=1,2,3,...,n

s[i]代表i号被涂几层   d[i]代表i号比i-1号多涂了几层

for(int i=1;i<=m;i++){
	cin>>a>>b;
	d[a]++;
	d[b+1]--;
}
for(int i=1;i<=n;i++)
	s[i]=s[i-1]+d[i];
cout<<*max_element(s+1,s+1+n)<<endl;

AC代码

#include <bits/stdc++.h>
using namespace std;
int n,m,d[200001],s[200001];
int main(){
    freopen("tape.in","r",stdin);
    freopen("tape.out","w",stdout);
    cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		d[a]++;
		d[b+1]--;
	}
	for(int i=0;i<n;i++)
		s[i]=s[i-1]+d[i];
	cout<<*max_element(s+1,s+1+n)<<endl;
	return 0;
}