借教室

时间：2019-09-08 12:30:43 收藏：0 阅读：49

【TIMEGate】

https://www.luogu.org/problem/P1083

【解题思路】

大致思路：利用差分数组存每天的教室使用情况，然后求前缀和，如果发现不符合要求，就从后往前撤回订单，直到每天都符合要求，那么我们撤回的最后一个（也就是最靠前的一个）即为ans

【code】

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 int n,m,l,r,last;
 6 int a[1000005],d[1000005],x[1000005],y[1000005],s[1000005];
 7 inline void read(int &x){
 8     char c=getchar();
 9     x = 0;
10     while(c<‘0‘||c>‘9‘)c=getchar();
11     while(c>=‘0‘&&c<=‘9‘){
12         x=(x<<1)+(x<<3)+(c^48);
13         c=getchar();
14     }
15     return ;
16 }
17 inline bool check(int m){
18     if(m>last)
19         for(register  int i=last+1;i<=m;i++){
20             s[x[i]]+=d[i];
21             s[y[i]+1]-=d[i];
22         }
23     else 
24             for(register int i=last;i>m;i--){
25                 s[x[i]]-=d[i];
26                 s[y[i]+1]+=d[i];
27             }
28     int sum=0;
29     for(register  int i=1;i<=n;i++){
30         sum+=s[i];
31         if(sum>a[i])return false;
32     }
33     return true;
34 }
35 int main(){
36     //freopen("classroom.in","r",stdin);
37     //freopen("classroom.out","w",stdout);
38     read(n);read(m);
39     for(register int i=1;i<=n;i++)
40         read(a[i]);
41     for(register int i=1;i<=m;i++)
42         read(d[i]),read(x[i]),read(y[i]);
43     l=1,r=m;
44     while(l<=r){
45         int mid=l+r>>1;
46         if(check(mid))l=mid+1;
47         else r=mid-1;
48         last=mid;
49     }
50     if(r==m)printf("0\n");
51     else {
52         printf("-1\n");
53         printf("%d\n",l);
54     }
55     return 0;
56 }

原文：https://www.cnblogs.com/66dzb/p/11485002.html