学步园

题目链接:  http://acm.hdu.edu.cn/showproblem.php?pid=2795

题目大意:    广告墙高从上到下为h，宽左到右为w，还有n张广告牌

                  用单位高度，宽度为wi的广告牌去覆盖墙

                  输出广告牌放的高度 (优先选择最上面的，同一高度则放在最左边)，不放不下则输出 -1

解题思路:   建立线段树，区间表示每个高度的剩余的宽度

                 最下层的结点(Tree[t].left==Tree[t].right)，存储这一层剩余的宽度MAX

                 其他结点存储左右子树的剩余宽度MAX

                 查询的时候，当此结点的MAX大于广告牌的宽度则往下查找

                 当左右子树都同时满足的情况下，优先选择左子树，若发现MAX不满足则停止搜索这棵子树

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max 210000
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b?a:b
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1+1)
typedef struct{
    int left,right;
    int leftmax,rightmax,max;
}Node;
Node Tree[Max<<2];
int n,h,w,pd,kk;
void Build(int t,int l,int r)                  //以1为根节点建立[l,r]的线段树
{
    int mid;
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].max=Tree[t].leftmax=Tree[t].rightmax=w;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
    Tree[t].leftmax=Tree[L(t)].max;
    Tree[t].rightmax=Tree[R(t)].max;
    Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);
}

void Query(int t,int l,int r,int m)
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r&&l==r)  //一直找到那个点l==r
    {
        if(Tree[t].max>=m)
        {
            Tree[t].max-=m;                      //找到那点，标记
            kk=Tree[t].left;
            pd=1;
        }
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(Tree[t].max<m)                            //若MAX小于m则退出，不搜索子树
        return ;
    if(Tree[t].leftmax>=m)                       //优先选择满足情况的左子树
        Query(L(t),l,mid,m);
    else if(Tree[t].rightmax>=m)                 //左子树不满足，才选择右子树
        Query(R(t),mid+1,r,m);
    else
        return ;
    Tree[t].leftmax=Tree[L(t)].max;
    Tree[t].rightmax=Tree[R(t)].max;
    Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);
}

int main()
{
    int i,m;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        if(h>n)
            h=n;
        memset(Tree,0,sizeof(Tree));    //初始化线段树
        Build(1,1,h);                   //建树
        for(i=0;i<n;i++)
        {
            scanf("%d",&m);
            pd=0;
            Query(1,1,h,m);             //查询[1,h]满足MAX>=n的区间
            if(pd)
                printf("%d\n",kk);
            else
                printf("-1\n");
        }
    }
    return 0;
}

注：原创文章，转载请注明出处