题意:有个公告板,大小为h*w,要贴n张公告,每个公告的长度是x,高度固定为1,公告放的要尽可能靠上并尽可能靠左,每给出一张公告,要求这个公告在满足要求的情况下放在了第几层。
Sample Input
3 5 5
2
4
3
3
3
Sample Output
1
2
1
3
-1
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <queue>
# define LL long long
using namespace std ; const int maxn = ; int MAX[maxn<<] ; //结点开4倍
int h , w , n ; void PushUP(int rt) //更新到父节点
{
MAX[rt] = max(MAX[rt * ] , MAX[rt * + ] ); //rt 为当前结点
} void build(int l , int r , int rt) //构建线段树
{
MAX[rt] = w ;
if (l == r)
{
return ;
}
int m = (l + r) / ;
build(l , m , rt * ) ;
build(m + , r , rt * +) ; } int query(int x , int l , int r , int rt) //区间求最大值的位子 直接把update的操作在query里做了
{
if (l == r)
{
MAX[rt] -= x ;
return l ; //每个叶子节点代表公告板的行
}
int m = (l + r) / ;
int ret = ;
if (MAX[rt * ] >= x)
ret = query(x , l , m , rt * ) ;
else
ret = query(x , m+ , r , rt * + ) ;
PushUP(rt) ;
return ret ;
} int main ()
{
//freopen("in.txt","r",stdin) ;
while(scanf("%d %d %d" , &h , &w , &n) != EOF) // h为高 w为宽 n为数量
{
if (h > n)
h = n ;
build( , h , );
while (n--)
{
int x ;
scanf("%d" , &x) ;
if (x > MAX[]) //如果一个公告的宽度 比1-h这区间 所有的剩余宽度都大 就是放不下了
printf("-1\n") ;
else
printf("%d\n" , query(x , , h , )) ;
}
} return ;
}