【问题描述】

2180 年奥运会竞技类分会场，将在XX 市举行。会场自然是政府的事情，我们就别操心了。艾瑞克却被兴奋而苦恼的情绪折磨着，他的宾馆是 XX 市最好的宾馆，近期旅客投宿的订单 m 份接踵而至，时间从 1~n 天，这代表着大把大把的银子，可是他最多只能提供 k 间客房，更多的他只能提前去租附近的房子并赶紧装修一下，时间很紧啊。

艾瑞克找到了他最好的朋友你：“哪，这是所有的订单，你给我在 1s 内计算出最高峰时，超出多少间客房，这样我才能知道得去租多少房子啊。”

每张订单包含 dj、sj、tj，表示从第 sj 日至第 tj 日，要预定 dj 个房间。为了简单起见，假设第一天之前宾馆所有的房间都是空的。

【输入】(hotelroom.in)

第一行包含两个正整数 n,m,k，表示天数、订单的数量，和现有客房数。

接下来有 m 行，每行包含三个正整数 dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。

 

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 1 开始的整数编号。

【输出】(hotelroom.out)

只有一个整数，表示最高峰时还差多少客房，客房足够输出 0（骗不到分）。

【样例输入】

【样例输出】

4 3 6

 

2 1 3

 

3 2 4

 

4 2 4

3

【数据范围】1<=n,m<=1000,000；1<=sj<=tj<=n；1<=k,dj<=1000； 输入数据较大，最好加读入优化

 

在解这道题之前，我们先要清楚什么是差分？

1.适合的操作/问题类型：大量的区间统一修改+单点查询；

2.建立一个差分数组，把[L，R]上的统一修改（统一加上某个量 x），反映到差分数组 c[L] 处加上 x， 在 c[R+1]处减去这个量 x，最后，要求某个点 a[i]的最终值，可对 c[i]求前缀和，再与 a[i]相加即可。 

解释一下题目：其实就是在[sj,tj]这个区间中增加dj的量。你先要把差分标记全部打好，然后求前缀和即可，再打个擂台，求个最大就OK

#include <bits/stdc++.h> using namespace std; int n,m,k,d,s,j,ans,sum; int a[100000+5]; inline int read()//快速读入 { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } int main() { n=read();m=read();k=read(); for(int i=1;i<=m;i++) { d=read();s=read();j=read(); //s=3,j=10,d=2; a[s]+=d;//开头加上这个增量 a[j+1]-=d;//结尾的下一个减去这个增量 } for(int i=1;i<=n;i++)//求前缀和 { sum+=a[i];//第i天对房间需求量 ans=max(ans,sum-k);//ans是全局变量，初始是0，所以即使是负的，也没得关系 } cout<<ans; return 0; }

PS：下面好好介绍一下差分

比如说我们会遇到这样的题目:在[3,10]这个区间，统一加上x，我们可能会想到用循环来解决。但如果是3到10000,3到1000000呢？遇到这种大量区间修改的，最好用差分。