其实就是求能满足多少个订单。。
然后搞上差分，
又因为如果前n个能够满足，那么前m个一定能满足（m<n）
所以可以二分（重点！）
然后乱搞。。就AC了（其实也挺麻烦的。。。233~）
下面贴代码
#include<iostream> #include<cstdio> #include<cstring> int n,m; int a[1000010],r[1000010],sum[1000010],bg[1000010],ed[1000010]; using namespace std; bool judge(int q){ memset(sum,0,sizeof(sum)); int s=0; for(int i=1;i<=q;i++) {sum[bg[i]]+=r[i];sum[ed[i]+1]-=r[i];} for(int i=1;i<=n;i++) {s+=sum[i];if(s>a[i]) return 0;} return 1; } int main(){ int ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d%d%d",&r[i],&bg[i],&ed[i]); int l=1; int r=m; while(l<=r) { int mid=l+r>>1; if(!(judge(mid))){ans=mid,r=mid-1;} else l=mid+1; } if(!ans)printf("0 "); else{printf("-1 "); printf("%d",ans);} return 0; }