题解 P1083 【借教室】
暴力
还是先看暴力怎么做吧，对于m次借教室，我们可以每次把区间s~t的空教室数r-=d，当有一次r<0时，则当前这个人无法被满足，直接输出-1和当前这个人的号数，然后直接结束程序。如果m次借教室都操作完成后依然没有房间数r<0，则说明所有人都可以被满足，则输出0。
综合上述做法+过大的数据直接输出0，得分45。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int r[1000005];
int d[1000005],s[1000005],t[1000005];
int main()
{
cin>>n>>m;
if(n>=100000)
{
cout<<0;
return 0;
}
for(int i=1;i<=n;i++)
cin>>r[i];
for(int i=1;i<=m;i++)
cin>>d[i]>>s[i]>>t[i];
for(int i=1;i<=m;i++)
{
for(int j=s[i];j<=t[i];j++)
{
r[j]-=d[i];
if(r[j]<0)
{
cout<<-1<<endl<<i;
return 0;
}
}
}
cout<<0;
return 0;
} 显然，这样做法的时间复杂度时O(N*M)的，无法通过此题，从而我们可以推知该题正确的时间复杂度应该是log级的。
正解
既然时间复杂度时log级的，于是想到了二分。
再看到每个人借教室的时间可以看成一个区间，且该区间只会对其他在该区间要借教室的人产生影响，对于区间之外的借教室的人是不会产生影响的，于是又想到了差分。
差分序列：（可用于区间增减）记录相邻两个量的变化量，所以当在一段区间[l,r]上增加a时，只需要在l处加a，在r+1处-a即可。
如果还不理解差分是个什么东东的，戳这里感受一下。。。
对于为什么可以二分：如果一个人无法被满足，则他后面的人全都不能被满足；如果一个人可以被满足，则他前面的人都可以被满足。这恰恰吻合了我们二分的性质。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;//天数和订单的数量
int r[1000005];//第i天学校有r[i]个教室可借用
int d[1000005],s[1000005],t[1000005];//借的教室数目、从第s天借到t天
int cf[1000005];//差分数组
bool judge(int x)//判断能不能通过x个人
{
memset(cf,0,sizeof(cf));//每次判断都要先初始化差分数组
int sum=0;//记录需要借的教室数
for(int i=1;i<=x;i++)
{
cf[s[i]]+=d[i];//因为只会对在s~l之间要借用教室的人产生影响，所以可以差分
cf[t[i]+1]-=d[i];//差分//注意是t[i]+1，因为要包含t[i]这个点
}
for(int i=1;i<=n;i++)
{
sum+=cf[i];//因为cf是差分数组，所以sum就是在第i天的借教室的总数
if(sum>r[i])//如果要借的教室多于空的教室
return false;//不可行
}
return true;//可行
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&d[i],&s[i],&t[i]);
if(judge(m)==true)//如果全部满足
{
cout<<'0';//输出0
return 0;//直接结束程序
}
int l=1;
int r=m;//二分左右区间
while(l<r)
{
int mid=(l+r)/2;
if(judge(mid)==true)//如果可行
l=mid+1;//增多满足人数
else//否则
r=mid;//减少满足人数
}
cout<<"-1"<<endl<<l;//输出-1和需要修改的人
return 0;
}如果有兴趣感受一下二分，戳这里
ps：那几个数组一定不要开大了，卡空间的。。。。