HDU 2795 Billboard（宣传栏贴公告，线段树应用）

ACM

题目地址：HDU 2795 Billboard

题意：
要在h*w宣传栏上贴公告，每条公告的高度都是为1的，而且每条公告都要尽量贴最上面最靠左边的，给你一系列的公告的长度，问它们能不能贴上。

分析：
不是很好想，不过想到了就很好写了。
只要把宣传栏倒过来就好办了，这时候就是变成有h条位置可以填公告，填放公告时就可以尽量找最左边的合适的位置来放了。
可以用线段树实现，查找的复杂度是O(logn)，需要注意的坑点是h的范围非常大，如果真的那么大线段树是开不下去的，但是n的范围才20w，而即使所有公告都要占一栏也不会超过n，所以线段树开min(h, n)就行了。

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2795.cpp
*  Create Date: 2014-08-05 16:12:47
*  Descripton:  segment tree 
*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) #define lson(x) ((x) << 1) #define rson(x) ((x) << 1 | 1) typedef long long ll; const int N = 200010; const int ROOT = 1; int h, w, n, t; // below is sement point updated version struct seg { ll w; }; struct segment_tree { seg node[N << 2]; void update(int pos) { node[pos].w = max(node[lson(pos)].w, node[rson(pos)].w); } void build(int l, int r, int pos) { if (l == r) { node[pos].w = w; return; } int m = (l + r) >> 1; build(l, m, lson(pos)); build(m + 1, r, rson(pos)); update(pos); } int queryandmodify(int l, int r, int pos, ll y) { if (y > node[pos].w) { return -1; } if (l == r) { node[pos].w -= y; return l; } int m = (l + r) >> 1; int res; if (y <= node[lson(pos)].w) res = queryandmodify(l, m, lson(pos), y); else res = queryandmodify(m + 1, r, rson(pos), y); update(pos); return res; } } sgm; int main() { while (~scanf("%d%d%d", &h, &w, &n)) { h = min(h, n); sgm.build(1, h, ROOT); repf (i, 1, n) { scanf("%d", &t); printf("%d\n", sgm.queryandmodify(1, h, ROOT, t)); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Codeforces 196 E. Opening Porta..	下一篇：HDU 1285 确定比赛名次（拓扑排序..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: