假设有100万张订单，我们先看第50万张订单能否满足，如果能满足，那么看第75万订单；如果不能满足，我们看第25万订单能否满足......一半一半，这就是二分。
但二分以后，还是会超时。一共两重循环，外循环做了二分，所以外循环是log2（1000000）。外循环第一次要把第一到第五十号全部全部遍历一遍，而内循环对每一张订单都要检查，最惨的情况，一张订单可能覆盖一号到1000000号...这样下来，远远超过一个亿，严重超时！！！
外循环已经做到了二分，如果内循环对每一张订单一张一张的检查，太慢了！但好在每一张订单是区间统一修改，这个时候就要做差分！！时间复杂度O(1)时间
#include <bits/stdc++.h> using namespace std; const int N=1000000+10;//一个上线，无论天数还是订单数都是1000000 struct node{ int x; int y; int z; }q[N]; int n,m,ans,a[N],b[N]; inline int read()//快速读入，订单不为负 { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x; } bool check(int x) { memset(b,0,sizeof(b)); int s=0; bool f=true; for(int i=1;i<=x;i++) { b[q[i].x]+=q[i].z; b[q[i].y+1]-=q[i].z; } for(int i=1;i<=n;i++) { s+=b[i]; if(s>a[i]) { f=false; break; } } return f; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read();//每一天可供租借的教室数量 for(int i=1;i<=m;i++) q[i].z=read(),q[i].x=read(),q[i].y=read();//x号~y号订z个房间 int l=1,r=m;//一共m张订单 while(l<=r) { int mid=(l+r)/2; if(!check(mid))//如果为假，说明当前订单不能满足，我们就要往前看，看有没有更小的订单不能满足。（题目问的是最小） { ans=mid; r=mid-1; } else l=mid+1; } if(!ans) cout<<"0"<<endl; //如果ans不为真，说明ans是个0，说明都能满足 else cout<<"-1"<<endl<<ans;//否则，找到一个不能满足的 return 0; }
写作不易，动个手，点个赞呗！我是新手中的新手，如有问题，还请指出！
