HDU 2795 - Billboard

传送门

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;
}

Powered by Jekyll and Theme by solid