[NOIP2016]借教室

NOIP2012提高组D2T2。

这道题目非常基础，正解貌似是二分+差分数组，在这里提供一种线段树的思路。

很容易发现题目让我们每次修改一段区间，然后我们只需要看每一个区间内有没有负数就可以了。可以用线段树维护每个区间内的最小值，修改的话就直接减就可以了，不要忘了标记下放（否则只有5分...）最后查看1-n内最小值是否为负数即可。

参考代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #define mid (l+r)/2

 #define lc k*2

 #define rc k*2+1

 using namespace std;

 int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}

     if(f)return x;return -x;

 }

 struct node

 {

     int l,r,tag,w;

 }tree[];

 int n,m,x,y,val,num;

 void pushup(int k){tree[k].w=min(tree[lc].w,tree[rc].w);}

 void build(int l,int r,int k)

 {

     tree[k].l=l;tree[k].r=r;

     if(l==r){tree[k].w=read();return;}

     build(l,mid,lc);build(mid+,r,rc);

     pushup(k);

 }

 void pushdown(int k)

 {

     tree[lc].tag+=tree[k].tag;tree[rc].tag+=tree[k].tag;

     tree[lc].w-=tree[k].tag;tree[rc].w-=tree[k].tag;

     tree[k].tag=;

 }

 void add(int k)

 {

     int l=tree[k].l,r=tree[k].r;

     if(l>=x&&r<=y)

     {

         tree[k].w-=val;

         tree[k].tag+=val;

         if(tree[k].w<)

         {

             cout<<-<<endl<<num<<endl;

             exit();

         }

         return;

     }

     if(tree[k].tag)pushdown(k);

     if(x<=mid)add(lc);

     if(y>mid)add(rc);

     pushup(k);

 }

 int main()

 {

     //freopen("classroom.in","r",stdin);

     //freopen("classroom.out","w",stdout);

     n=read();m=read();

     build(,n,);

     for(int i=;i<=m;i++)

     {

         num=i;val=read();x=read();y=read();

         add();

     }

     cout<<<<endl;

     //fclose(stdin);

     //fclose(stdout);

     return ;

 }

成功做完关于classroom的题目：NOIP2012D2T2借教室，NOIP2016D1T3换教室......

巴特西

[NOIP2016]借教室

最新文章

热门文章