首页 > 代码库 > 线段树入门（Billboard）

线段树入门（Billboard）

2024-07-02 09:51:10   226人阅读

Billboard

Time Limit:8000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

 

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

 

Sample Output

 

1
2
1
3
-1
线段树的水题。。
【题目大意】
有一个高和宽分别为h和w的广告牌，初始时牌子为空，然后在上面贴广告，每条广告的高都为1，宽为Wi，只能横着贴，位置的优先级为：上->左，输入一系列广告的宽，输出该条广告锁在的行数，如果贴不下了就输出-1。
【题目分析】
首先分析题目的思路，一开始可能会想到很多的方法，其实暴力模拟也可以，但是看看题目的数据：200,000，暴力模拟的话时间复杂度O(n^2)，妥妥的TLE了，所以要用到树状数组来优化时间复杂度，线段树的功能是维护区间的最大值，即：query:区间求最大值的位子(直接把update的操作在query里做了)，也就是每一行剩余的空格的最大值。
分析到这儿，题目就变得简单多了。
source code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAX 200010
using namespace std;
int h,w,n,a;
struct Node
{
    int l,r;
    int len;
} Tree[MAX*4];

void build(int l,int r,int x)
{
    Tree[x].l=l;
    Tree[x].r=r;
    Tree[x].len=w;//初始化的时候空格的长度都是w
    if(Tree[x].l==Tree[x].r)
        return;
    int mid=(l+r)>>1;
    build(l,mid,2*x);
    build(mid+1,r,2*x+1);
    Tree[x].len=Tree[2*x].len>Tree[2*x+1].len?Tree[2*x].len:Tree[2*x+1].len;//更新最大值
}
int query(int num,int x)
{
    if(Tree[x].l==Tree[x].r)
    {
        Tree[x].len-=num;//更新线段树最底层的值
        return Tree[x].l;//返回行数
    }
    int ans;
    if(num<=Tree[2*x].len)//小于左子树的长度，访问左子树
        ans=query(num,2*x);
    else if(num<=Tree[2*x+1].len)
        ans=query(num,2*x+1);
    Tree[x].len=Tree[2*x].len>Tree[2*x+1].len?Tree[2*x].len:Tree[2*x+1].len;//向上更新父节点的值
    return ans;
}
int main()
{
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        a=h<n?h:n;//只需要处理n和h中最小的行数
        build(1,a,1);
        int x;
        while(n--)
        {
            scanf("%d",&x);
            if(x>Tree[1].len)     //如果输入的广告长度比剩余最大的宽度还要大，则无解
                printf("-1\n");
            else
                printf("%d\n",query(x,1));
        }
    }
    return 0;
}

 

 
 
 
 
 

 


联系
我们