题解 | #[NOIP2012]借教室#

二分+差分即可； AC代码+注释如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{//结构体
    int d,s,t;
}a[N];
int n,m,b[N],c[N];

bool check(int x){//二分搜索
    for(int i=1;i<=n;i++)c[i]=0;//初始化
    for(int i=1;i<=x;i++){//差分
        c[a[i].s]+=a[i].d;
        c[a[i].t+1]-=a[i].d;
    }
    int t=0;
    for(int i=1;i<=n;i++){
        t+=c[i];//差分前缀和
        if(b[i]-t<0)return true;//判断是否满足矛盾
    }
    return false;
}

int main(){
    cin>>n>>m;//输入
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=m;i++)cin>>a[i].d>>a[i].s>>a[i].t;
    int l=1,r=m,ans=0;
    while(l<=r){//二分
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans)cout<<-1<<'\n'<<ans<<'\n';
    else cout<<ans<<'\n';//输出
}