即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

hdu2795 Billboard 线段树维护最值

编程语言 fanhansheng 15℃ 0评论

题意:在一个h*w的矩阵中, 放置n个1* wi的矩阵,矩阵是水平放入,尽量往原矩阵的左上放(下面不能为空,像叠砖头一样)。


求每一次放入的高度。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a) memset(a, 0, sizeof(a))
using namespace std;
typedef pair<int, int> Pii;
typedef long long LL;
const int MAXN = 800005;//20w没过,改大过了
const int inf = 0x3f3f3f3f;
const int Mod = 100000000;
struct node
{
    int l, r;
    LL w;
} tree[MAXN];
LL ans;
void build(LL k, LL l, LL r, LL w)
{
    tree[k].l=l;
    tree[k].r=r;
    tree[k].w=w;
    int mid = (l+r)>>1;
    if(tree[k].l==tree[k].r)
        return;
    build(k<<1|1,mid+1, r, w);
    build(k<<1, l, mid, w);
    return ;
}
void Insert(LL k, LL num)
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].w-=num;
        ans=tree[k].l;
        return;
    }
    if(num<=tree[k<<1].w)
        Insert(k<<1, num);
    else
        Insert(k<<1|1, num);
    tree[k].w=max(tree[k<<1|1].w, tree[k<<1].w);
    return;
}
int main()
{
    LL n, h, w;
    LL num;
    while(~scanf("%lld %lld %lld", &h, &w, &n))
    {
        if(h>n)
            h=n;
        build(1,1,h,w);
        for(int i=1; i<=n; ++i)
        {
            scanf("%lld", &num);
            ans=-1;
            if(num<=tree[1].w)
                Insert(1, num);
            printf("%lld\n", ans);
            ans=-1;
        }
    }
    return 0;
}

转载请注明:CodingBlog » hdu2795 Billboard 线段树维护最值

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情