线段树 Ⅱ 朴灿烈づ我的快乐病毒、 2022-08-03 13:45 308阅读 0赞 单点修改(内容有升级) \[hdu2795\] ([http://acm.hdu.edu.cn/showproblem.php?pid=2795][http_acm.hdu.edu.cn_showproblem.php_pid_2795]) 题目描述: Billboard(公告板) Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15079 Accepted Submission(s): 6421 Problem Description At the entrance to the university, there is a huge rectangular(矩形的) billboard of size h\*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information. On September 1, the billboard was empty. One by one, the announcements started being put on the billboard. Each announcement is a stripe(条纹) of paper of unit(单元) height. More specifically, the i-th announcement is a rectangle(矩形) of size 1 \* wi. When someone puts a new announcement on the billboard, she would always choose the topmost(最高) possible position for the announcement. Among all possible topmost positions she would always choose the leftmost(最左) one. If there is no valid location for a new announcement, it is not put on the billboard (that’s why some programming contests have no participants from this university). Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed. Input There are multiple cases (no more than 40 cases). The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions(规模,大小) of the billboard and the number of announcements. Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement. Output For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows(行数) are numbered from 1 to h, starting with the top row. If an announcement can’t be put on the billboard, output “-1” for this announcement. Sample Input 3 5 5 2 4 3 3 3 Sample Output 1 2 1 3 \-1 分析: 题目大意是给一个h\*w的公告牌,h是高度,w是宽度,一个单位高度1为一行,然后会有一些公告贴上去,公告是1\*wi大小的长纸条,优先贴在最上面并且最左边的位置,如果没有空间贴得下,就输出-1,可以的话,就输出所贴的位置(第几行)。 叶节点\[x,x\]表示board的第x行还可以放置的长度,区间\[a,b\]表示第a行到b行中剩下空间最大的那一行是多少,如果要把长w的公告放入 board时就是update,优先往左子树走(如果左子树的空间足够的话),一直走到叶节点,更新这个叶节点剩下的长度,然后再向上更新。 #include <iostream> #include <stdio.h> using namespace std; const int N=200005; int w; struct node { int l,r,mid;//表示左端点,右端点,中点 int ma;//表示节点内的最大值 }tree[N*4]; int max(int a,int b) { return a>b ? a:b; } int min(int a,int b) { return a<b ? a:b; } void build(int l,int r,int root) { tree[root].l=l; tree[root].r=r; tree[root].mid=(l+r)/2; tree[root].ma=w;//选宽度为节点内的最大值 if(l==r)//建立递归到叶子节点 { return; } build(l,(l+r)/2,root<<1);//建立左儿子直到叶子节点 build((l+r)/2+1,r,root<<1|1);//建立右儿子直到叶子节点 } int updata(int board,int root) { if(tree[root].l==tree[root].r)//表示当前公告板上第l行还能放置的长度 { tree[root].ma-=board;//将广告单的长度减去 return tree[root].l; } int ret; if(tree[root<<1].ma>=board)//优先在左儿子中找到空位,并把它放下 { ret=updata(board,root<<1); } else ret=updata(board,root<<1|1); tree[root].ma=max(tree[root<<1].ma,tree[root<<1|1].ma); return ret; } int main() { int h,n,a; while(scanf("%d%d%d",&h,&w,&n)!=EOF) { build(1,min(h,n),1);//取h和n的最小值,作为右端点,从root=1开始来建树 for(int i=1;i<=n;i++) { scanf("%d",&a); if(tree[1].ma<a) printf("-1\n"); else printf("%d\n",updata(a,1)); } } return 0; } [http_acm.hdu.edu.cn_showproblem.php_pid_2795]: http://acm.hdu.edu.cn/showproblem.php?pid=2795
相关 线段树 线段树:创建时实际做的是后序遍历 > 1. 线段树不是完全二叉树 > 2. 线段树是平衡二叉树 > 3. 堆也是平衡二叉树,故完全二叉树是平衡二叉树,平衡二叉树不一 朱雀/ 2023年07月10日 12:39/ 0 赞/ 23 阅读
相关 线段树 [http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html][http_www.cnblogs.com_s 迈不过友情╰/ 2022年09月20日 09:13/ 0 赞/ 290 阅读
相关 线段树 1、概述 线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段(即“子数组”),因而常用于解决数列维护问题,它基本能保证每个操作的复杂度为O(lgN)。 2、线段 分手后的思念是犯贱/ 2022年08月10日 10:53/ 0 赞/ 249 阅读
相关 线段树 Ⅱ 单点修改(内容有升级) \[hdu2795\] ([http://acm.hdu.edu.cn/showproblem.php?pid=2795][http_acm.hdu 朴灿烈づ我的快乐病毒、/ 2022年08月03日 13:45/ 0 赞/ 309 阅读
相关 线段树 线段树:一棵完全二叉树,每个节点代表一个区间。 关于单点更新: \[hdu1166 \] ([http://acm.hdu.edu.cn/showproblem.php?p ﹏ヽ暗。殇╰゛Y/ 2022年08月03日 13:45/ 0 赞/ 301 阅读
相关 线段树 线段树入门: 转载博客:[点击打开链接][Link 1] 前几天开始接触线段树,其一些基本的操作还是很容易理解的,但是区间更新我着实理解了好一会(因该是本人太菜),今天有时 Myth丶恋晨/ 2022年05月29日 22:16/ 0 赞/ 349 阅读
相关 线段树 一 概述 线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(l 川长思鸟来/ 2022年05月17日 05:53/ 0 赞/ 330 阅读
相关 线段树 线段树(单点修改) 1 include <bits/stdc++.h> 2 using namespace std; 3 4 stru 亦凉/ 2021年12月03日 07:17/ 0 赞/ 405 阅读
相关 线段树 转载 [https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html][https_www.cnblogs.com_TheRo 心已赠人/ 2021年07月16日 15:21/ 0 赞/ 539 阅读
还没有评论,来说两句吧...