Billboard（线段树）

Billboard

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

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（1到10^9），宽W（1到10^9）的公告栏。给出N（1到200000）张海报，每张海报都是1*w的大小，给出这N张海报的w大小，张贴的要求是在满足不超过总长度W的基础上尽力往上贴，输出海报所在的行数，如果这张海报无论如何也无法张贴，则输出-1。

 

       思路：

       简单模拟无疑会TLE，所以要用线段树来做。对1到h进行线段树处理，H的范围是（1到10^9）而N范围是（1到200000），所以如果H>N的话就算每张海报贴一行最多也只用到N行的高度，所以首先先处理H，如果H>N则H=N。用max域来登记行区间的最大剩余量，查询的时候如果海报宽度大于区间最大宽度则ans=-1返回，如果不大于则先访问左儿子是否大于海报宽度，如果是则先访问左儿子。因为张贴要求是尽量往上贴，那就是行数尽量少，所以优先访问左儿子。

       

       TLE：

#include<stdio.h>
#define MAX 200000+5
__int64 num[MAX];
int main()
{
	__int64 h,w,n;
	while(scanf("%I64d%I64d%I64d",&h,&w,&n)!=EOF)
	{
		for(__int64 i=1;i<=h;i++)
			num[i]=w;
		for(__int64 i=1;i<=n;i++)
		{
			int temp=0;
			__int64 we;
			scanf("%I64d",&we);
			for(int j=1;j<=h;j++)
			{
				if(num[j]-we>=0)
				{
					temp=1;
					printf("%I64d\n",j);
					num[j]-=we;
					break;
				}
			}
			if(!temp)	printf("-1\n");
		}
	}
	return 0;
}

 

       AC：

#include<stdio.h>
#include<stdlib.h>
#define MAX 1000000
typedef struct
{
	__int64 l;   //左边界
	__int64 r;   //右边界
	__int64 max; //最大值
}node;
node no[MAX*3];
__int64 w,ans;

void build(__int64 from,__int64 to,__int64 i)
{
	__int64 mid=(from+to)/2;
	no[i].l=from;
	no[i].r=to;
	no[i].max=w;   //初始化为最大宽度
	if(from==to) return; 
	build(from,mid,2*i);
	build(mid+1,to,2*i+1);
}

__int64 find(__int64 from,__int64 to,__int64 a,__int64 i)
{
	__int64 mid=(from+to)/2;
	if(a>no[i].max)
	{
		ans=-1;
		return 0;  //返回0并结束函数
	}
	if(from==to&&a<=no[i].max)
	{
		no[i].max-=a;
		ans=from;
		return no[i].max;
	}
	if(a<=no[2*i].max) find(from,mid,a,2*i);
	else			   find(mid+1,to,a,2*i+1);
	no[i].max=(no[2*i].max>no[2*i+1].max?no[2*i].max:no[2*i+1].max);
}

int main()
{
	__int64 h,n;
	while(scanf("%I64d%I64d%I64d",&h,&w,&n)!=EOF)
	{
		if(h>n) h=n;
		build(1,h,1);
		while(n--)
		{
			__int64 we;
			scanf("%I64d",&we);
			find(1,h,we,1);
			printf("%I64d\n",ans);
		}
	}
	return 0;
}

 

 

       总结：

       1.想清楚隐含条件；

       2.注意写法；

__int64 find(__int64 from,__int64 to,__int64 a,__int64 i)
{
	__int64 mid=(from+to)/2;
//这一部分
	if(a>no[i].max)
	{
		ans=-1;
		return 0;
        }
//一开始是写成if(a>no[i].max)  return 0;的
//忘了将ans赋值为-1了，所以ans输出来还是上一次的结果值
	if(from==to&&a<=no[i].max)
	{
		no[i].max-=a;
		ans=from;
		return no[i].max;
//这里一开始写return from;了
//其实无论return什么也没有关系，关键是一定要记得先对ans赋值
//如果在主函数中调用函数是ans=find(……)的话，return的值就有关系了
	}
	if(a<=no[2*i].max) find(from,mid,a,2*i);
	else	           find(mid+1,to,a,2*i+1);
	no[i].max=(no[2*i].max>no[2*i+1].max?no[2*i].max:no[2*i+1].max);
}

       3.注意分析时间复杂度。