P1083 [NOIP2012 提高組] 借教室 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

思路：二分+前綴和

我們將和質檢員那題差不多，只需要將候選人二分即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int r[1000005];
int d[1000005];
int s[1000005];
int t[1000005];
int dif[1000005];
int sum[1000005];//差分數組的前綴和數組，統計每天至少要有多少凳子(需求數組 
bool check(int x)//x表示的是訂單數 
{memset(dif,0,sizeof(dif));for(int i=1;i<=x;i++){dif[s[i]]+=d[i];dif[t[i]+1]-=d[i];}for(int i=1;i<=n;i++){sum[i]=sum[i-1]+dif[i];if(sum[i]>r[i])return false;}return true;
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>r[i];}for(int i=1;i<=m;i++){cin>>d[i]>>s[i]>>t[i];}if(check(m)){cout<<0;return 0;}cout<<-1<<"\n";int l=1,r=m;int mid;while(l<=r){mid=(l+r)/2;if(check(mid)){l=mid+1;}else{r=mid-1;}}cout<<l;return 0;
}