这道题一开始看,实在想不出跟线段树有什么关系,自己实在是太菜了。

给出h*w的广告版。每个广告是1*w的,给出m个广告,要每张广告尽量在上层尽量靠左,输出它所在的高度。假设放不下。就输出-1

这里的问题就是h给的非常大,可是 一共仅仅有m个广告,所以即使是一条广告占一条,那么也就仅仅须要m的高度,多余的高度没实用,假设m的高度的不能放下m条广告,那么即使h再高,也放不下,所以n应该是m和h的小值。一段存储下它所控制的区间的最大值,仅仅要最大值大于广告wi,那么第i条广告就能够放到这个区间内。 先推断左子树。左子树不合适后推断右子树(放上面),除非是当前的wi大于整段的最大值。否则一定能够放到广告版内,注意:在放入一个广告之后,改动全部的父节点的最大值。

 

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 200005
int hh[maxn<<2];
int h, w, n;
void pushup(int root){
	hh[root] = max(hh[root<<1],hh[root<<1|1]);
}
void build(int root, int l, int r){
	hh[root] = w;
	if(l == r) {
		return;
	}
	int m = (r+l)>>1;
	build(root<<1, l, m);
	build(root<<1|1, m+1, r);
}
int que(int root, int l, int r, int x){
	if(l == r){
		hh[root] -= x;
		return l;
	}
	int m = (r+l)>>1;
	int ans;
	ans = hh[root<<1] >= x ? que(root<<1, l, m, x) : que(root<<1|1, m+1, r, x);
	pushup(root);
	return ans;
}
int main() {
	while(~scanf("%d%d%d",&h,&w,&n)){
		h = min(h,n);
		build(1,1,n);
		int x;
		while(n--) {
			scanf("%d",&x);
			if(hh[1] < x){
				printf("-1\n");
			}else {
				printf("%d\n",que(1,1,h,x));
			}
		}
	}
	return 0;
}

 

先推断左子树。左子树不合适后推断右子树,除非是当前的wi大于整段的最大值。否则一定能够放到广告版内,注意,在放入一个广告之后,改动全部的父节点的最大值。