题目链接:https://www.luogu.com.cn/problem/P1083
因为有一个时间截点,在这个截点的前面,总是能满足教室的要求,而在这个截点的后面,都不能满足教室的要求,所以可以二分枚举这一个时间截点。
AC代码:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int N=1000005; 6 int n,m; 7 struct node{ 8 int d,s,t; 9 }q[N]; 10 int d[N],s[N],r[N]; 11 bool check(int x){ 12 memset(d,0,sizeof(d)); 13 memset(s,0,sizeof(s)); 14 for(int i=1;i<=x;i++){ 15 d[q[i].s]+=q[i].d; 16 d[q[i].t+1]-=q[i].d; 17 } 18 for(int i=1;i<=n;i++) s[i]=s[i-1]+d[i]; 19 for(int i=1;i<=n;i++){ 20 if(s[i]>r[i]) return 0; 21 } 22 return 1; 23 } 24 int main(){ 25 scanf("%d%d",&n,&m); 26 for(int i=1;i<=n;i++) scanf("%d",&r[i]); 27 for(int i=1;i<=m;i++){ 28 scanf("%d%d%d",&q[i].d,&q[i].s,&q[i].t); 29 } 30 int l=1,r=m; 31 while(l<r){ 32 int mid=(l+r)>>1; 33 if(check(mid)) l=mid+1; 34 else r=mid; 35 } 36 if(l==m) { printf("0\n"); return 0;} 37 printf("-1\n%d",l); 38 return 0; 39 }AC代码