首页 > 代码库 > hdu2795--Billboard

hdu2795--Billboard

2024-07-23 11:42:39   211人阅读

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2795

摘要：有一块尺寸为h*w的矩形长板，要在上面贴1*wi的海报n张，选择贴海报的位置是：尽量高，同一高度，选择尽量靠左的地方。要求输出每张海报的高度位置。

直接用线段树来做就可以了，用线段树维护 区间剩余位置的最大宽度。

#include <set>#include <map>#include <cmath>#include <ctime>#include <queue>#include <stack>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef unsigned long long ull;typedef long long ll;const int inf = 0x3f3f3f3f;const double eps = 1e-8;const int maxn = 2e5+10;int h,w,n,seg[maxn<<2],tot[maxn<<2];void build(int l,int r,int pos){    if (l == r)    {        seg[pos] = w;        tot[pos] = l;        return;    }    int mid = (l + r) >> 1;    build(l,mid,pos<<1);    build(mid+1,r,pos<<1|1);    seg[pos] = max(seg[pos<<1],seg[pos<<1|1]);}int query(int l,int r,int pos,int x){    if (l == r)    {        if (seg[pos] >= x)        {            seg[pos] -= x;            return l;        }    }    int mid = (l + r) >> 1;    int ans;    if (seg[pos<<1] >= x)    {        ans = query(l,mid,pos<<1,x);    }    else if (seg[pos<<1|1] >= x)    {        ans = query(mid+1,r,pos<<1|1,x);    }    seg[pos] = max(seg[pos<<1],seg[pos<<1|1]);    return ans;}int main(void){    #ifndef ONLINE_JUDGE        freopen("in.txt","r",stdin);    #endif    while (~scanf ("%d%d%d",&h,&w,&n))    {        int wi;        if (h > n)            h = n;        build(1,h,1);        for (int i = 0; i < n; i++)        {            scanf ("%d",&wi);            if (wi>seg[1])                printf("-1\n");            else                printf("%d\n",query(1,h,1,wi));        }    }    return 0;}

　　

hdu2795--Billboard


联系
我们