题解 | #[NOIP2012]借教室#

二分检验

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct student{
	int num;
	int be;
	int en;
};
student a[1001000];
int room[1001000];
int pre[1001000];
int ans,l,r,mid,n,day,cnt;
bool check(int mid){
	memset(pre,0,sizeof(pre));
	for(int i = 1;i<=mid;i++){
		pre[a[i].be]+=a[i].num;
		pre[a[i].en+1]-=a[i].num;
	}
	for(int i = 1;i<=day;i++){
		pre[i]+=pre[i-1];
		if(pre[i]>room[i])return 0;
	}
	return 1;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>day>>n;
	for(int i = 1;i<=day;i++)cin>>room[i];
	for(int i = 1;i<=n;i++)cin>>a[i].num>>a[i].be>>a[i].en;
	if(check(n)){
		cout<<0;
		return 0;	
	}	
	l=0;r=n+1;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;
		}else{
			ans=mid;r=mid-1;
		}
	}
	cout<<ans;
}