hdu 2795 Billboard（线段树）

hdu 2795 Billboard（线段树）

题目：​​题意：给一个h*w的广告牌，一个单位高度是一行，然后有一些公告贴上去，公告是1*wi的大小的长纸条，优先贴在左上方，如果空间不满足就输出-1，可以的话就输出位置（第几行）

类似的区间问题首先想到的是线段树。但是这里要以行数为着眼点，left是上行数，right是下行数，把wi设为结点内的一个数据成员。最后写出found子函数，水到渠成。

#include #include#includeusing namespace std;int w;const int maxn=2e5+5;struct node{ int l,r,mid,length;}d[3*maxn];void build(int s,int e,int dex){ d[dex].l=s; d[dex].r=e; d[dex].mid=(s+e)/2; d[dex].length=w; if(d[dex].l==d[dex].r)return ; build(s,d[dex].mid,dex*2); build(d[dex].mid+1,e,dex*2+1);}int found(int b,int dex){ if(d[dex].l==d[dex].r){ d[dex].length-=b; return d[dex].l; } int ans; if(b<=d[dex*2].length)ans=found(b,dex*2); else ans=found(b,dex*2+1); d[dex].length=max(d[dex*2].length,d[dex*2+1].length); return ans;}int main(){ //freopen("cin.txt","r",stdin); int h,n,i,board; while(~scanf("%d%d%d",&h,&w,&n)){ build(1,min(h,n),1); for(i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。