首页 > 代码库 > HDU 2795 Billboard(线段树)
HDU 2795 Billboard(线段树)
题目链接:HDU 2795 Billboard
【题意】给你一张h*w(1 <= h,w <= 10^9)大小的海报,上面会张贴一些数量为n(1<=n<=200000)高度为1宽度不定的小纸条,然后输入一些小纸条的宽度,求出它所张贴的高度。小纸条张贴是尽量靠左靠上,如果不能张贴,就输出-1.
【思路】海报的数据特别大,思路就是用线段树来优化,但是高度h高达10^9,直接建树肯定会爆,但纸条最多有n(200000)张,于是可以用len = min(h, n)来进行建线段树[1, len],节点维护的是海报每一行的可利用空白宽度。每次查询优先往左子树查询,查询之后还要更新数据,保留新的可利用空白宽度。
【吐槽】第一次自己来写线段树,以前对线段树一直是一种仰望的心态,的确是很牛逼的算法,有二分的思想在里面,转换为logn的强大力量。但是真的不好写啊数据结构就是伤不起。
下面贴AC代码:
1 /* 2 ** HDU 2795 Billboard 3 ** Created by Rayn @@ 2014/05/08 4 ** 线段树 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <algorithm> 9 using namespace std; 10 const int MAX = 200005; 11 12 int tree[MAX<<2]; 13 14 void BuildTree(int k, int l, int r, int val) 15 { 16 tree[k] = val; 17 if(l == r) 18 return ; 19 int mid = (l + r) / 2; 20 BuildTree(k<<1, l, mid, val); 21 BuildTree(k<<1|1, mid+1, r, val); 22 } 23 int Query(int k, int l, int r, int val) 24 { 25 if(l == r && tree[k] >= val) 26 { 27 tree[k] -= val; 28 return l; 29 } 30 int mid = (l + r) / 2, ans; 31 if(tree[k<<1] >= val) 32 ans = Query(k<<1, l, mid, val); 33 else if(tree[k<<1|1] >= val) 34 ans = Query(k<<1|1, mid+1, r, val); 35 else 36 ans = -1; 37 tree[k] = max(tree[k<<1], tree[k<<1|1]); 38 return ans; 39 } 40 int main() 41 { 42 int h, w, n; 43 while(scanf("%d%d%d", &h, &w, &n) != EOF) 44 { 45 h = min(h, n); 46 BuildTree(1, 1, h, w); 47 for(int i=0; i<n; ++i) 48 { 49 int wid; 50 scanf("%d", &wid); 51 printf("%d\n", Query(1, 1, h, wid)); 52 } 53 } 54 return 0; 55 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。