?

Problem : 2795 ( Billboard ) ????Judge Status : Accepted
RunId : 5864258????Language : C????Author : qq1203456195

?

/* 題意：高h寬w的公告欄，往上邊貼1*L的公告，在能放的區域內按照最上最左的原則 張貼。 輸出：每張公告貼分別在了第幾行。 ========================================================================= 每個結點存儲的是當前l-r行上能貼的公告的L的最大值Max if(Max>=L)說明可以放 {if(MaxL>=L)進入左子樹;else進入右子樹; } else {不能放，返回; } */ #include <stdio.h> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define MAX 222222 int Max[MAX<<2],n,h,w;//公告數量，高度(使用的高度不會超過n)，寬度 void build(int l,int r,int rt) {int m;Max[rt]=w;if(l==r){Max[rt]=w;return;}m=((l+r)>>1);build(lson);build(rson); } int max(int a,int b) { return a>=b?a:b;} int post(int p,int l,int r,int rt) {int m,ret=0;if (l==r){Max[rt]-=p;return l;}m=((l+r)>>1);if(Max[rt<<1]>=p)ret=post(p,lson);elseret=post(p,rson);Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);return ret; } int main() {int i,p;while (~scanf("%d%d%d",&h,&w,&n)){if(h>n)h=n;build(1,h,1);for (i=0;i<n;i++){scanf("%d",&p);if(Max[1]<p)printf("-1\n");elseprintf("%d\n",post(p,1,h,1));}} return 0; }

?

轉載于:https://www.cnblogs.com/CheeseZH/archive/2012/04/28/2475767.html

總結

以上是生活随笔為你收集整理的HDOJ2795 Billboard【线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。