题目分析：给你n张海报，一个宣传板。让你在满足海报能够贴在最高位置的时候则贴的最高，无法满足时贴的最靠左，输出海报所贴的高度。假设不能贴则输出-1.
一道非常easy，可是我没想出的基础线段树。
算法思想：
把宣传板的高度转换成线段树的区间，从而得知每个区间的大小当然为宣传板的宽度啦。然后，每次查询每个区间内的大小是否有满足当前海报宽度的，有责得到结果。然后，在更新减去当前所用的宽度。依据线段是的特点，我们知道我们会先得到小的答案，即，较高的高度（高度从1-h）。
另一个须要处理的就是，当高度超过200000的时候，要截取。由于海报最多才200000，所以不须要那么高的宣传板。
#include#include #include #include using namespace std;#define L(rt) (rt << 1)#define R(rt) (rt << 1 | 1)#define MID(a,b) (a+((b-a) >> 1))#define lson lft,mid,rt << 1#define rson mid+1,rht,rt << 1 | 1const int MAXN = 222222;struct Node{ int lft,rht,mx; int mid(){return MID(lft,rht);};};Node tree[MAXN*4];int w,h,n;class Segtree{public: void Build(int lft,int rht,int rt){ tree[rt].lft = lft;tree[rt].rht = rht; tree[rt].mx = w; if(lft != rht){ int mid = tree[rt].mid(); Build(lson); Build(rson); } } int Update(int rt,int val){ int lft = tree[rt].lft,rht = tree[rt].rht; if(lft == rht){ tree[rt].mx -= val; return lft; } else{ int pos; if(tree[L(rt)].mx >= val)pos = Update(L(rt),val); else pos = Update(R(rt),val); tree[rt].mx = max(tree[L(rt)].mx,tree[R(rt)].mx); return pos; } }};int main(){ while(~scanf("%d%d%d",&h,&w,&n)){ Segtree seg; seg.Build(1,min(h,MAXN),1); for(int i = 0;i < n;++i){ int wid; scanf("%d",&wid); if(tree[1].mx < wid)printf("-1\n"); else printf("%d\n",seg.Update(1,wid)); } } return 0;}