hdu 2795(线段树)

解题思路：这道题很难想到是用线段树，确实转化的很巧妙

实际上，我们只需要利用线段树（记录1-h）维护哪个位置的剩余空间最大即可，即1,2,......,h是线段树的叶子节点，我们每次要找的就是叶子节点的剩余空间的最大值，只要能够想到这里就很容易啦。。另外如果h>n的话，就令h=n，否则就是类似于位置多而要贴上去的砖少，这样就不合题目意思了。。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 200005;
struct seg
{
	int l,r,value,id;
}tree[maxn<<2];
int h,w,n;

void build(int l,int r,int u)
{
	tree[u].l = l;
	tree[u].r = r;
	tree[u].value = w;
	tree[u].id = l;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(l,mid,2*u);
	build(mid+1,r,2*u+1);
}

void update(int l,int r,int v,int u)
{
	if(tree[u].l >= l && tree[u].r <= r){
		tree[u].value -= v;
		return;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	if(l <= mid) update(l,r,v,2*u);
	if(r > mid) update(l,r,v,2*u+1);
	if(tree[2*u].value >= tree[2*u+1].value){
		tree[u].value = tree[2*u].value;
		tree[u].id = tree[2*u].id;
	}
	else{
		tree[u].value = tree[2*u+1].value;
		tree[u].id = tree[2*u+1].id;
	}
}

int query(int v,int u)
{
	if(tree[u].value < v) return -1;
	if(tree[u].l == tree[u].r) return tree[u].id;
	if(tree[2*u].value >= v) 
		return query(v,2*u);
	else return query(v,2*u+1);
}

int main()
{
	int x;
	while(scanf("%d%d%d",&h,&w,&n)!=EOF)
	{
		if(h > n) h = n;
		build(1,h,1);
		for(int i = 1; i <= n; i++){
			scanf("%d",&x);
			int tmp = query(x,1);
			if(tmp != -1){
				printf("%d\n",tmp);
				update(tmp,tmp,x,1);
			}
			else printf("-1\n");
		}
	}
	return 0;
}