题意:给定一个h*w广告牌,给定n个1*wi 的公告,贴公告的规则是,如果上面能贴尽量往上面贴,如果如果左边能贴尽量往左边贴,问你每个广告牌所在的行数;
解题思路,对n建树,然后动态维持区间最大值,查找更新!
解题代码:
1 #include2 #include 3 #include 4 #include 5 #define MAXN 200005 6 struct node 7 { 8 int left ,right ,mid; 9 long long num;10 }tree[4*MAXN];11 int h , w, n ;12 int L(int c)13 {14 return 2*c ;15 }16 int R(int c )17 {18 return 2*c + 1;19 }20 void up(int c)21 {22 tree[c].num = tree[L(c)].num >tree[R(c)].num ?tree[L(c)].num :tree[R(c)].num;23 }24 void build(int c , int p , int v )25 {26 tree[c].left = p ;27 tree[c].right = v ;28 tree[c].mid = (p+v)/2;29 tree[c].num = 0 ;30 if(p == v)31 {32 tree[c].num = w ;33 return;34 }35 build(L(c),p,tree[c].mid);36 build(R(c),tree[c].mid+1,v);37 up(c);38 }39 int ok = 0 ;40 void F(int c, int value )41 {42 if(tree[c].num >= value )43 {44 //printf("%d\n",tree[c].left);45 if(tree[c].left == tree[c].right)46 {47 ok = tree[c].left;48 tree[c].num -= value ;49 return ;50 }51 if(tree[L(c)].num >= value )52 F(L(c),value);53 else54 F(R(c),value);55 up(c);56 }57 }58 59 60 int main()61 {62 while(scanf("%d %d %d",&h,&w,&n) != EOF )63 {64 if(n >h )65 build(1,1,h);66 else67 build(1,1,n);68 for(int i = 1; i <= n;i ++)69 {70 int value ;71 scanf("%d",&value);72 ok = 0 ;73 74 F(1,value);75 if(ok != 0 )76 printf("%d\n",ok);77 else78 printf("-1\n");79 }80 }81 return 0 ;82 }