借教室
题目链接
https://www.luogu.com.cn/problem/P1083
解题思路
第一种方法,也是我用的方法,因为另一种没想到。
线段树,维护区间最小值,比较简单,就是代码冗长
不会戳这里
第二种才是好方法,差分数组+二分
这道题就是我点差分数组才找到的,说来惭愧我并没用差分数组。
将二分请求出错是第几次,
check函数的话,从第一次请求到二分的这次请求循环,用差分数组记录,再循环1 ~ n求和,并比较与房间个数的大小关系,比房间多说明不可行,否则可行。
AC代码
//线段树 维护最小值 区间修改 区间查询 //提醒用scanf,printf否则可能超时 #include<bits/stdc++.h> using namespace std; const int N=1e6+10; const int INF=0x3f3f3f3f; int n,m,d,s,t,ans,j,rm[N]; struct TREE { int l,r,lazy,m; }tr[N<<2]; void Build(int i,int l,int r) { tr[i].l=l; tr[i].r=r; tr[i].lazy=0; tr[i].m=INF; if(l==r) { tr[i].m=rm[l]; return ; } int mid=l+r>>1; Build(i<<1,l,mid); Build(i<<1|1,mid+1,r); tr[i].m=min(tr[i<<1].m,tr[i<<1|1].m); return ; } void PushDown(int i) { if(tr[i].lazy==0) return ; tr[i<<1].lazy+=tr[i].lazy; tr[i<<1|1].lazy+=tr[i].lazy; tr[i<<1].m-=tr[i].lazy; tr[i<<1|1].m-=tr[i].lazy; tr[i].lazy=0; } void Update(int i,int l,int r,int sub) { if(l<=tr[i].l && tr[i].r<=r) { tr[i].lazy+=sub; tr[i].m-=sub; return ; } PushDown(i); if(tr[i<<1].r>=l) Update(i<<1,l,r,sub); if(tr[i<<1|1].l<=r) Update(i<<1|1,l,r,sub); tr[i].m=min(tr[i<<1].m,tr[i<<1|1].m); return ; } int Query(int i,int l,int r) { if(l<=tr[i].l && tr[i].r<=r) return tr[i].m; if(tr[i].r<l || tr[i].l>r) return INF; int res=INF; PushDown(i); if(tr[i<<1].r>=l) res=min(res,Query(i<<1,l,r)); if(tr[i<<1|1].l<=r) res=min(res,Query(i<<1|1,l,r)); tr[i].m=min(tr[i<<1].m,tr[i<<1|1].m); return res; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&rm[i]); Build(1,1,n); for(j=1;j<=m;j++) { scanf("%d%d%d",&d,&s,&t); if(d>Query(1,s,t))//d大于区间最小值 break { ans=j; break; } Update(1,s,t,d); //维护区间最小值 } if(j>m) puts("0"); else puts("-1"),printf("%d\n",ans); return 0; } //差分数组+二分 #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int diff[N],rm[N],d[N],l[N],r[N],sum[N]; int n,m; bool check(int x) { memset(diff,0,sizeof diff);//! for(int i=1;i<=x;i++) { diff[l[i]]+=d[i]; diff[r[i]+1]-=d[i]; } for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+diff[i]; if(sum[i]>rm[i]) return 0; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&rm[i]); for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&l[i],&r[i]); if(check(m)) puts("0"); else { int ll=1,rr=m; while(ll<rr) { int mid=ll+rr>>1; if(check(mid)) ll=mid+1; else rr=mid; } puts("-1");printf("%d",ll); } return 0; }