随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

HDU 2795 Billboard

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2795
/*
题意:
    对于w*h(w <= 10^9, h <= 10^9 )的一块区域,连续摆放1*wi的木板,木板不能
旋转,如果能放下就选择最靠上的位置摆放,并且输出行号,如果找不到直接输出-1。

解法:
线段树

思路:
    将h这一维映射到线段树的区间,w这一维则对应区间点上的最大值,每次询问时
做一次插入操作,如果当前访问的结点的最大值小于给定值,直接返回-1。否则,左
子树的最大值大于当前值,那么访问左子树,小于则访问右子树,直到叶子结点。如
果成功找到,说明给定值小于叶子结点的值,将叶子结点的值减去给定值,然后递归
更新内部结点的最值。
*/


#include 
<iostream>

using namespace std;

#define maxn 200010

struct Tree {
    
int Max;
    
int root, l, r;
}
T[maxn*4];

int h, w, n;
void Build(int p, int l, int r) {
    T[p].root 
= p;
    T[p].l 
= l;
    T[p].r 
= r;
    T[p].Max 
= w;
    
if(l == r) {
        
return ;
    }

    
int mid = (l + r) >> 1;
    Build(p
<<1, l, mid);
    Build(p
<<1|1, mid+1, r);
}


int MMax(int a, int b) {
    
return a > b ? a : b;
}


int Insert(int p, int val) {
    
if(T[p].l == T[p].r) {
        
if(T[p].Max < val)
            
return -1;
        T[p].Max 
-= val;
        
return T[p].l;
    }


    
if(val <= T[p].Max) {
        
int x = 0;
        
if(val <= T[p<<1].Max) {
            x 
= Insert(p<<1, val);
        }
else {
            x 
= Insert(p<<1|1, val);
        }

        T[p].Max 
= MMax(T[p<<1].Max, T[p<<1|1].Max);
        
return x;
    }
else
        
return -1;
}


int main() {
    
int i, X;
    
while(scanf("%d %d %d"&h, &w, &n) != EOF) {
        
if(h > n)
            h 
= n;

        Build(
11, h);
        
for(i = 0; i < n; i++{
            scanf(
"%d"&X);
            printf( 
"%d\n", Insert(1, X) );
        }

    }

    
return 0;
}

posted on 2011-04-03 18:32 英雄哪里出来 阅读(1325) 评论(0)  编辑 收藏 引用 所属分类: 线段树


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