题解 | #借教室#

本题要找第几个安排是无法完成的，可以反着想，设前k个订单是符合要求的，因此把前k个订单的l，r加到一个空数组中，则这个数组前k个数的每个值都应该小于等于每天的空教室数量，每次从l加到r，会超时，所以联想一下，从l到r每个数都加上一个数，这正是差分。要找到这个k，可以用二分算法，因为若前k个订单满足，则前k个每个订单一定满足，第k+1个开始一定不满足。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int a[N],n,m,d[N],l[N],r[N],b[N];
bool check(int mid)
{
    memset(b,0,sizeof b);
    for(int i=1;i<=mid;i++)//差分操作
    {
        b[l[i]]+=d[i];
        b[r[i]+1]-=d[i];
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=b[i];//sum为第i个
        if(sum>a[i])return false;
    }
    return true;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&d[i],&l[i],&r[i]);
    int l=0,r=m;
    while(l<r)//用找较大值的模板
    {
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    if(r==m)cout<<0;
    else cout<<-1<<endl<<r+1<<endl;
    return 0;
}