【NOIP2012 提高组 day2】借教室

教室"/>

【NOIP2012 提高组 day2】借教室

题目

题解

–首先，这道题用线段树是可以过得，luogu上最慢的点也才700ms，具体就不说了
主要讲更快的二分加差分的方法
–首先，差分是一种对区间修改的优化，可以把时间复杂度降到只跑一遍
重点是二分，因为对于某个点，如果不满足，那么不满足的点一定是它，或是它的前方的某个点
如果满足，那就一定在后面
其实是单调的
就可以用二分来做

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1e6+5;int n,m;
int r[MAXN];
int d[MAXN],s[MAXN],t[MAXN];
int cf[MAXN];bool ok(int x){memset(cf,0,sizeof(cf));for(int i=1;i<=x;i++){cf[s[i]]+=d[i];cf[t[i]+1]-=d[i];}for(int i=1;i<=n;i++){cf[i]+=cf[i-1];if(cf[i]>r[i])return 0;}return 1;
}int main(){
//  freopen("classroom.in","r",stdin);
//  freopen("classroom.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&r[i]);for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);if(ok(m)){cout<<0;return 0;}int L=1,R=m;while(L<R){int mid=(L+R)/2;if(ok(mid))L=mid+1;elseR=mid;}cout<<-1<<endl<<R;return 0;
}