分析题干,要找出是否有订单无法满足,就又可以用二分查找来进行检验,就是假设你已经知道了答案,答案为x,现在就是要接近这个x.然后是先输入n和m,表示有n天,m个订单,接着输入n个数来表示那天可以借的教室的数量,然后输入m行表示对应订单的借dj个教室从sj到tj天.

对于订单来说我们可以设置结构体来存储数据

当读取到第i个订单时,那么从si天到tj天教室就少了dj个,但是其他天不影响,因此我们可以想到使用差分数组来进行处理,下标表示的是天数,其内容表示的是剩余教室的数量.

#include<iostream>
using namespace std;
const int N=1e6+10;
struct ding
{
	int d,s,t;
}ding[N];
int n,m,r[N],delta[N];
bool judge(int x)
{
	for(int i=1;i<=n;i++)
    	delta[i]=r[i]-r[i-1];
    for(int i=1;i<=x;i++)
    {
    	delta[ding[i].s]-=ding[i].d;
        delta[ding[i].t+1]+=ding[i].d;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
    	sum+=delta[i];
        if(sum<0)return false;
    }
    return true;
}
int main()
{
	cin>>n>>m;
    for(int i=1;i<=n;i++)
    	cin>>r[i];
    for(int i=1;i<=m;i++)
    	cin>>ding[i].d>>ding[i].s>>ding[i].t;
    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>m) cout<<0;
    else cout<<"-1"<<endl<<l;
    return 0;
}