题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2795

解题思路

虽然做的是线段树专题，甚至直到要维护区间最大值，但是依然不知道怎么实现。
虽然题目很简单，但思想不好想。
画个图吧，不好说。

也就是维护的是l ~ r行中的所有行中剩余空间的最大值。

AC代码

放了俩代码
代码1是用结构体实现的tree数组
代码2是用参数实现tree左右端点的
习惯哪个看哪个吧

//代码1
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int h,w,n,wi;
struct TREE
{
    int l,r,res;    
}tr[N<<2];
void Build(int i,int l,int r)
{
    tr[i].l=l;
    tr[i].r=r;
    tr[i].res=w;//初始剩余空间的最大值为w
    if(l==r) return ;
    int mid=l+r>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
    return ;
}
int Query(int i,int wii)
{
    int res;
    if(tr[i].l==tr[i].r)
    {
        tr[i].res-=wii;
        return tr[i].l;
    }
    if(tr[i<<1].res>=wii) res=Query(i<<1,wii);//if语句中是左子树的剩余最大空间是否大于等于wii
    else res=Query(i<<1|1,wii);
    tr[i].res=max(tr[i<<1].res,tr[i<<1|1].res);//！！！
    return res;
}
int main()
{
    while(~scanf("%d%d%d",&h,&w,&n))
    {
        if(h>n) h=n;
        Build(1,1,h);//！！注意右边是h，不是h<<2（应该只是我傻）
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&wi);
            if(tr[1].res<wi) puts("-1");
            else printf("%d\n",Query(1,wi));
        }
    } 
    return 0;
}


//代码2
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+100;
int tr[N<<2],wi,h,w,n;
int Query(int i,int l,int r,int wii)
{
    if(l==r)
    {
        tr[i]-=wii;
        return l;
    }
    int mid=l+r>>1,res;
    if(tr[i<<1]>=wii) res=Query(i<<1,l,mid,wii);
    else res=Query(i<<1|1,mid+1,r,wii);
    tr[i]=max(tr[i<<1],tr[i<<1|1]);//！！！
    return res;
}
int main()
{
    while(~scanf("%d%d%d",&h,&w,&n))
    {
        if(h>n) h=n;
        for(int i=1;i<=(h<<2);i++) tr[i]=w;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&wi);
            if(wi>tr[1]) puts("-1");
            else printf("%d\n",Query(1,1,h,wi));
        }
    }

    return 0;
}

总结

做的前几个线段树的题目都是纯板子题，这次稍微见识到如何运用线段树降低时间复杂度了。
说到底，线段树只是一种工具，而不是算法。
就本题而言，纯数组模拟当然可以，甚至用线段树实现的过程也是在模拟，但是由于线段树的特性，使得时间复杂度降低，优化了算法。