描述
题解
这道题读懂题的话就很直观了……
给定一个 h*w 的矩形广告板,然后往上边贴广告,贴的原则是尽量靠上并且尽量靠左,那么很直观的想到线段树,对 h 进行建树,h 不必太大,只要保证 ≤n 即可,因为尽量靠上嘛,对于尽量靠左也就是说,每一行如果可以贴多个广告,那么一定是肩并肩靠左贴,所以把 w 作为初始容量存入树中即可,每贴一个广告,减去一个广告长度即可,最后,查找时,如果左子树可以贴,就优先左子树,否则右子树,这是为了保证靠上原则。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 200000 + 10;
int h, w, n;
int a[MAXN << 2];
void build(int l, int r, int u)
{
a[u] = w;
if (l == r)
{
return ;
}
int m = (l + r) >> 1;
build(l, m, u << 1);
build(m + 1, r, u << 1 | 1);
}
int query(int x, int l, int r, int u)
{
if (l == r)
{
a[u] -= x;
return l;
}
int res = 0;
int m = (l + r) >> 1;
if (a[u << 1] >= x)
{
res = query(x, l, m, u << 1);
}
else
{
res = query(x, m + 1, r, u << 1 | 1);
}
a[u] = max(a[u << 1], a[u << 1 | 1]);
return res;
}
int main()
{
while (~scanf("%d%d%d", &h, &w, &n))
{
if (h > n)
{
h = n;
}
build(1, h, 1);
int x;
while (n--)
{
scanf("%d", &x);
if (a[1] < x)
{
printf("-1\n");
}
else
{
printf("%d\n", query(x, 1, h, 1));
}
}
}
return 0;
}