首页 > 代码库 > HDU 2795 线段树（转变思维方能改变世界）

HDU 2795 线段树（转变思维方能改变世界）

2024-07-13 04:03:42   227人阅读

Billboard

Time Limit: 20000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9895    Accepted Submission(s): 4413


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
 
 
 
题目意思：
输入3个数字h,w,n
在宽为h，长为w的木板上贴n张海报，每张海报的宽为1，长度不确定。
以下n行为每次贴的海报的长。
贴海报时必须优先贴木板左上方（海报不能重叠），若贴上了，输出该海报贴的位置的行（行即为木板的宽上面的数字，宽的最上面为1，从上往下依次增加1），反之输出-1。
 
思路：
若按平常思维，就是每次贴海报就从第一行开始，看是否能贴，若能则贴，不能则判断下一行，直到最后一行，若实在贴不下输出-1.
代码太复杂了，实现难度也太大，那怎么办呢，就需要打破常规，转换一下思维方式。
 
若把木板转一下，使得原来的长变成宽，原来的宽变成长。那么贴海报不就成了盖楼了吗，若能贴，则这一列的高度h=h+海报的长度，否则则判断下一列。把转置后得木板的宽当作区间段，这不就是单点增加么，代码就好些的多了，贴海报的过程即为先序遍历了。细节：输入的木板的宽和列都太大，建树需要离散化吗？一般来说需要离散化，但本题说贴海报的时候优先贴木板左上方，给的操作次数n可以当作列数，因为若m张海报全部贴上，最多也只能贴m列。
 
代码：
 
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 #define N 200005 7  8 struct node{ 9     int l, r;10     int h;11 }a[N*4];12 13 int h, w;14 15 void build(int left,int right,int root){16     a[root].l=left;17     a[root].r=right;18     a[root].h=0;19     if(left==right) return ;20     int mid=(left+right)/2;21     build(left,mid,root*2);22     build(mid+1,right,root*2+1);23 }24 25 int update(int height,int root){26     if(a[root].h+height>w) return -1;27     if(a[root].l==a[root].r){28         a[root].h+=height;29         return a[root].l;30     }31     int t=update(height,root*2);32     if(t==-1) t=update(height,root*2+1);33     if(t!=-1) a[root].h=min(a[root*2].h,a[root*2+1].h);34     return t;35 }36 main()37 {38     int n;39     int i, j, k, ww;40     while(scanf("%d %d %d",&h,&w,&n)==3){41         if(h>200000) h=200000;42         build(1,h,1);43         while(n--){44             scanf("%d",&ww);45             printf("%d\n",update(ww,1));46             47         }48     }49 }

 


联系
我们