HDU2795

题意是给你一个h*w的广告板，然后有n张1*wi的广告要贴上去，要求尽可能的左，相同的情况下尽可能靠上。

我们可以按照层数来建立线段树，然后每一部分记录最大的w值。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <queue>
#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)
using namespace std;

const int INF=999999999;
const int maxn=222222;

int h,w;
int Max[maxn<<2];

void build(int o,int L,int R)
{
	Max[o]=w;
	if(L==R)
		return;
	int M=(L+R)/2;
	build(o*2,L,M);
	build(o*2+1,M+1,R);
}

int query(int o,int L,int R,int num)
{
	if(L==R)
	{
		Max[o]-=num;
		return L;
	}
	int M=(L+R)/2,ans;
	if(Max[o*2]>=num)
		ans=query(o*2,L,M,num);
	else
		ans=query(o*2+1,M+1,R,num);
	Max[o]=max(Max[o*2],Max[o*2+1]);
	return ans;
}

int main()
{
	int n,m;
	while(scanf("%d%d",&h,&w)!=EOF)
	{
		scanf("%d",&n);
		if(h>n)
			h=n;
		build(1,1,h);
		while(n--)
		{
			scanf("%d",&m);
			if(Max[1]<m)
				printf("-1\n");
			else
				printf("%d\n",query(1,1,h,m));
		}
	}
	return 0;
}

HDU2795,布布扣,bubuko.com

HDU2795

原文：http://blog.csdn.net/mfmy_szw/article/details/21050127