https://www.luogu.org/problem/show?pid=1083#sub

一開始容易想到的方法是線段樹，每次修改時，如果出現負數，那么當前這個人一定不能滿足了。
但是在noip里，這肯定不是正解，所以會超時那么一兩個點。

#include<iostream> #include<cstdio> #include<cmath> #include<stdlib.h> #define M 1000000 using namespace std; int n,m,cnt; int a[M+100]; struct H{int x,l,r,len,addi; }st[5*M]; inline int read() {int data=0,w=1; char ch=0;while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') w=-1,ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data*w; } void build(int o,int l,int r) {st[o].l=l,st[o].r=r,st[o].len=r-l+1;if(l==r){st[o].x=a[l];return;}int mid=(l+r)>>1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);st[o].x=min(st[o<<1].x,st[o<<1|1].x); } void pushdown(int o) {st[o<<1].addi+=st[o].addi;st[o<<1|1].addi+=st[o].addi;st[o<<1].x+=st[o].addi;st[o<<1|1].x+=st[o].addi; st[o].addi=0; } void add(int o,int ql,int qr,int ax) {int l=st[o].l,r=st[o].r,mid=(l+r)>>1;if(l==ql&&r==qr){st[o].addi+=ax;st[o].x+=ax;if(st[o].x<0){printf("-1\n%d",cnt);exit(0);}return;}if(st[o].addi) pushdown(o);if(qr<=mid) add(o<<1,ql,qr,ax);else if(ql>mid) add(o<<1|1,ql,qr,ax);else add(o<<1,ql,mid,ax),add(o<<1|1,mid+1,qr,ax);st[o].x=min(st[o<<1].x,st[o<<1|1].x); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,1,n); for(int i=1;i<=m;i++){int d,s,t;cnt=i;//scanf("%d%d%d",&d,&s,&t);d=read();s=read();t=read();add(1,s,t,-d);}printf("0\n");return 0; }

那么正解是什么呢–>二分答案。
判定的寫法是，對前mid個人操作，加上差分，最后看看是否有小于0的，有則r=mid-1，否則l=mid+1；
這樣一直判定。最后如果l>=n，就說明全部都能滿足；否則答案就是 l 。

#include<iostream> #include<cstdio> #define M 1000000 using namespace std; int n,m,a[M+10],b[M+10]; int d[M+10],s[M+10],t[M+10]; bool check(int x) {for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];for(int i=1;i<=x;i++) b[s[i]]-=d[i],b[t[i]+1]+=d[i];for(int i=1;i<=n;i++) {b[i]+=b[i-1];if(b[i]<0) return false;}return true; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=m;i++) scanf("%d%d%d",&d[i],&s[i],&t[i]);int l=1,r=n,mid;while(l<=r){mid=(l+r)>>1;if(check(mid)) l=mid+1;else r=mid-1;}if(l>=n) printf("0");else printf("-1\n%d",l);return 0; }

轉載于:https://www.cnblogs.com/dfsac/p/7587867.html

總結

以上是生活随笔為你收集整理的P1083 [NOIP 2012]借教室的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。