The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

HDOJ 2795 Billboard 简单线段树

     很显而易见的线段树,只是有一点需要注意,题目中虽然给了h的范围可以达到10^9,但是由于布告总共只有200000条,最坏情况下只需要200000个线段树的叶子节点,所以可以直接无视h的范围,线段树总结点开200000*4即可。维护的时候,注意利用回溯,自底向上地更新。
    
#include<iostream>
using namespace std;
int const maxn=200010;

int h,w,n;
int num[maxn];
struct node
{
    
int size;
    
int l,r;
}
ST[maxn*6];

void creat(int l,int r,int i)
{
    ST[i].l
=l;
    ST[i].r
=r;
    
if(l==r)
    
{
        ST[i].size
=w;
        
return;
    }

    
int mid=(l+r)>>1;
    creat(l,mid,i
*2);
    creat(mid
+1,r,i*2+1);
    ST[i].size
=w;
}


int ans;
void Query(int i,int x)
{
    
if(ST[i].l==ST[i].r)
    
{
        ans
=ST[i].l;
        ST[i].size
-=x;
        
return ;
    }

    
if(ST[i*2].size>=x)
        Query(i
*2,x);

    
else if(ST[i*2+1].size>=x)
        Query(i
*2+1,x);
    ST[i].size
=max(ST[i*2].size,ST[i*2+1].size);
}


int main()
{

    
while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    
{
        creat(
1,min(h,200000),1);
        
for(int i=0;i<n;i++)
        
{

            
int x;
            scanf(
"%d",&x);
            
if(ST[1].size<x)
                printf(
"-1\n");
            
else
            
{

                Query(
1,x);
                printf(
"%d\n",ans);
            }


        }



    }

    
return 0;


}

posted on 2010-10-22 23:29 abilitytao 阅读(1349) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理