题解 | #借教室#

二分k+差分检查

我们可以把每天能借的教室数量用数组存下来。当第i天到第j天需要借出k间教室时，a[i]到a[j]的数都减k。这样就能用差分数组来完成。
若前k份订单可以，则前面k-1份都可以；若第k份不行，则后面都不行，因此想到二分
每次都对前k份订单用差分数组维护，看看是否会减成负数

这里用的差分数组并不是严格意义上的差分，而可以理解成是相对于原数组的差分。
例如，原数组a为1 2 8 3 5 （下标从1开始），现在需要把下标2到4的数都减1
这时候，差分数组d可以表示为0 -1 0 0 1
那么如何求之后的数组a呢？
以a中下标0的元素为参照（假设它存在且保持不变），由于d[1]=0,因此a[1]相对于a[0]不变,a[1]'=1。
d[2]=-1,表明a[2]相对a[1]减小了1，相对a[0]也减小了1,a[2]'=1
d[3]=0，表明a[3]相对a[2]不变，由于a[2]相对a[0]减小1，因此a[3]相对a[0]减小1
即a[3]'=7
同理a[4]'=2
d[5]=1，表明a[5]相对a[4]增加了1，则相对a[0]不变，即a[5]不变
综上，a[0]也可以理解成是原本的这个数，d[1]+...+d[i]，算出来就是a[i]'相对原先的a[i]变化了多少
所以由差分构造r'数组的代码就出来了：

for(int i=1;i<=n;i++){
        cha[i]+=cha[i-1];
        r1[i]+=cha[i];
    }

先求出差分的前缀，再与原来的数相加，即可实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int r[1000010],d[1000010],s[1000010],t[1000010];
int n,m;
bool judge(int mid){
    int cha[1000010]={0};//差分数组
    int r1[1000010]={0};
    for(int i=1;i<=n;i++)     r1[i]=r[i];//拷贝数组r 
    for(int i=1;i<=mid;i++){
        cha[s[i]]-=d[i];
        cha[t[i]+1]+=d[i];
    }
    for(int i=1;i<=n;i++){
        cha[i]+=cha[i-1];
        r1[i]+=cha[i];
        if(r1[i]<0)        return false;//教室不够分 
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> r[i];
    }
    for(int i=1;i<=m;i++){
        cin >> d[i] >> s[i] >> t[i];
    }
    int l=0,r=m;
    while(l<=r){
        int mid=(l+r)>>1;
        if(judge(mid))    l=mid+1;
        else            r=mid-1;
    }
    if(l-1==m)    cout << "0\n";
    else{
        cout << "-1\n";
        cout << l << "\n";
    }
    return 0;
}