HDU 2795 - Billboard
传送门
题意
一个布告板有宽W高H,一个布告高度都是1,现在有N个布告要贴,从第一行开始贴,尽量靠左。给出宽度,输出所在行数。
思路
就算知道这题是线段树我也想了一会儿。原来这样也可以用线段树解,好奇妙。
用线段树维护某个区间的最大宽度,把一行看做一个点。在询问的同时更新。
代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define lowbit(x) ((x) & (-x))
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f;
struct SEG
{
int l, r, wMax;
}segT[MAXN << 2];
int w;
int PushUp(int cur)
{
segT[cur].wMax = max(segT[cur << 1].wMax, segT[cur << 1 | 1].wMax);
}
int GetMid(int m, int n)
{
return m + ((n - m) >> 1);
}
void Build(int cur, int l, int r)
{
segT[cur].l = l, segT[cur].r = r;
if (l == r)
{
segT[cur].wMax = w;
return;
}
int mid = GetMid(l, r);
Build(cur << 1, l, mid);
Build(cur << 1 | 1, mid + 1, r);
PushUp(cur);
}
int Query(int cur, int val)
{
if (segT[cur].wMax < val)
return -1;
if (segT[cur].l == segT[cur].r)
{
segT[cur].wMax -= val;
return segT[cur].l;
}
int mid = GetMid(segT[cur].l, segT[cur].r);
int ans = 0;
if (segT[cur << 1].wMax >= val)
ans = Query(cur << 1, val);
else
ans = Query(cur << 1 | 1, val);
PushUp(cur);
return ans;
}
int main()
{
//freopen("input.txt", "r", stdin);
int h, n, i, j, a;
while (~scanf("%d%d%d", &h, &w, &n))
{
Build(1, 1, min(n, h));
while (n--)
{
scanf("%d", &a);
printf("%d\n", Query(1, a));
}
}
return 0;
}