借教室 题解

题目：共N天，M个订单，第 i 天有 $r_i$ 间教室可以用。对于每 i 条订单，有$d_i, l_i$和$r_i$分别表示该订单需要的教室数量，从某一天开始租借和租借到某一天。订单讲究先来后到。问是否可以满足所有订单，若不满足则输出-1以及第一个不满足的订单编号。

看到这道题，首先我们可以想到暴力：
直接从第一个订单枚举到最后一个订单，看看哪个订单不满足。
但是，由于我们每次判断都需要枚举一遍求出他们的租借情况，所以：
时间复杂度：$O(nm)$，显然会超时。

于是乎，我们可以开始对这道题进行观察：

关键观察：答案情况成单调性

用人话来说，就是：当第 i 个订单不满足时，第 i+1 到 第 m 个订单都是不满足的。
因为只要前面会出现不合法的情况，后面的订单都会继承这个不合法的情况。

所以，如果我们用$check(i)$表示第 i 个订单是否合法，我们就可以得到$check$的刻画情况：

$true\space true\space true\space ...\space false\space false\space ...$

注意到，这样的单调情况可以使用二分快速求解。
于是，我们的$check(x)$使用暴力算出$1$~$x$的租借情况，再使用二分。
时间复杂度：$O((n+m)logm)$，不会超时

代码：

void solve(){
    ll n,m;
    cin>>n>>m;
    vector<ll>r(n+1,0);
    vector<ll>diff(n+2,0);
    for(int i = 1;i<=n;i++){
        cin>>r[i];
    }
    struct node{
        ll d,l,r;
    };
    vector<node>a(m+1,{0,0,0});
    for(int i =1;i<=m;i++){
        cin>>a[i].d>>a[i].l>>a[i].r;
    }
    auto check = [&](int id){
        vector<ll>v;
        v = diff;
        for(int i = 1;i <= id;i++){
            v[int(a[i].l)]+=a[i].d;
            v[(int)a[i].r+1]-=a[i].d;
        }
        for(int i = 1;i<=n;i++){
            v[i]+=v[i-1];
        }
        for(int i = 1;i<=n;i++){
            if(v[i]>r[i]){
                return false;
            }
        }
        return true;
    };
    int l1 = 1,r1 = m,ans = -1;
    while(l1<=r1){
        int mid = (l1+r1)>>1;
        if(check(mid)){
            l1 = mid+1;
        }else{
            r1 = mid-1;
            ans = mid;
        }
    }
    if(ans != -1){
        cout<< -1 << '\n' << ans << '\n';
    }else{
        cout<<0<<'\n';
    }
}