P1083 借教室

题目链接https://www.luogu.com.cn/problem/P1083

一、5分题解：

1 #include<bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5     cout<<0;
6     return 0;
7  }

View Code

二、纯模拟（45分）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int a[1000005];
 5 int d, s, t;
 6 int f=0, ans;
 7 int main()
 8 {
 9     cin>>n>>m;
10     for(int i=1; i<=n; i++)
11         cin>>a[i];
12     for(int i=1; i<=m; i++){
13         cin>>d>>s>>t;
14         for(int j=s; j<=t; j++){
15             a[j]-=d;
16             if(a[j]<0){
17                 f=-1;
18                 break;
19             }
20         }
21         if(f!=0){
22             ans=i;
23             break;
24         }
25     }
26     if(f==0)cout<<0;
27     else cout<<f<<endl<<ans;
28     return 0;
29  }

三、前缀和、差分、二分答案（100分）

　　思路：从第一份订单开始枚举，直到无法满足或者全枚举完结束

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int diff[1000005], a[1000005], d[1000005], s[1000005], t[1000005];
 5 int ans=-1;
 6 int l, r;
 7 bool isok(int mid){
 8     memset(diff, 0, sizeof(diff));
 9     for(int i=1; i<=mid; i++){
10         diff[s[i]]-=d[i]; 
11         diff[t[i]+1]+=d[i];
12     }
13     int temp=0;
14     for(int i=1; i<=n; i++){
15         temp+=diff[i];
16         if(a[i]+temp<0)return 0;
17     }
18     return 1;
19 }
20 int main()
21 {
22     cin>>n>>m;
23     for(int i=1; i<=n; i++)cin>>a[i];
24     for(int i=1; i<=m; i++)cin>>d[i]>>s[i]>>t[i];
25     l=1; r=m;
26     while(l<=r){
27         int mid=(l+r)/2;
28         if(!isok(mid)){
29             ans=mid;
30             r=mid-1;
31         }
32         else {
33             l=mid+1;    
34         }
35     }
36     
37     if(ans==m || ans==-1)cout<<0;    
38     else cout<<-1<<endl<<ans;
39     
40     return 0;
41 }