从前往后看,看不能满足的是哪个订单,输出不能第一个不满足的订单编号
因为如果不满足直接输出-1,后面就不用看,即可用二分的思想来看
每次操作是区间内加上一个数或者减去一个数,判断区间内是否有数小于0,差分,可以做到线性
#include<iostream>
using namespace std;
typedef long long LL; //数量都是10^9级别,做前缀和或者差分会爆int
const int N=1e6+10;
int n,m; //n,m表示天数和订单的数量。
int r[N],d[N],s[N],t[N]; //r表示每天可以租的教室数量,d表示每天需要租的教室数量,s表示开始天,t表示结束天
LL b[N]; //差分数组
bool check(int mid)
{
for(int i=1;i<=n;i++) b[i]=r[i]-r[i-1]; //先处理差分数组
for(int i=1;i<=mid;i++)
{
b[s[i]]-=d[i];
b[t[i]+1]+=d[i];
}
for(int i=1;i<=n;i++)
{
b[i]+=b[i-1];
if(b[i]<0) return true; //表示不能满足
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>r[i];
for(int j=1;j<=m;j++){
cin>>d[j]>>s[j]>>t[j];
}
if(!check(m)) //判断是否前m天都可以满足,输出0,放在前面少些二分,check(m)=false 表示差分数组b没有小于0,都满足
{
puts("0");
return 0;
}
//二分看第一个不能满足的天是哪天
int l=1,r=m; //因为有m次操作,在里面二分
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;// 如果不能满足说明x在mid左边,x为第一个不能满足的
else l=mid+1; //如果可以满足说明x在mid的右边
}
printf("-1\n%d",r); //有不满足的,输出这一天r
return 0;
}