这道题的思路还是很好想的，就是维护一个差分数组，这样可以很容易的在O（n）的时间内计算出每天要的教室的数量。
之后的问题在于……怎么求最早的不符合要求的订单呢？
那就是老套路啦，二分答案！
先判断一下所有的都加上可不可行，如果不可行，我们二分那个不合法订单的编号，把所有在它之前的都加上，并且判定能不能满足即可。
这个正确性还是很显然的。看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; const int M = 1000005; typedef long long ll; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct lend { ll d,s,t; }a[M]; ll n,m,ro[M],l,r,mid,cha[M]; bool check(int x) { memset(cha,0,sizeof(cha)); ll cur = 0; rep(i,1,x) cha[a[i].s] += a[i].d,cha[a[i].t+1] -= a[i].d; rep(i,1,n) { cur += cha[i]; if(cur > ro[i]) return 0; } return 1; } int main() { n = read(),m = read(); rep(i,1,n) ro[i] = read(); rep(i,1,m) a[i].d = read(),a[i].s = read(),a[i].t = read(); if(check(m)) { printf("0 "); return 0; } else { l = 1,r = m; while(l < r) { mid = (l + r) >> 1; if(check(mid)) l = mid + 1; else r = mid; } } printf("-1 %lld ",l); return 0; }