HDU 2795 Billboard.(线段树)

By admin in 编程 on 2019年8月27日

HDU 2795 Billboard.(线段树)

难点连接:


开始学习数据结构,从简单的开始吧,刷题累了就写解题报告,哈哈,沸腾吧,Segment
tree!

粗粗题意:一块
h*w的广告牌,蓝后就算n块1*wi大小的广告,依次贴到广告牌上,并且连连贴到最左上角,问贴完全体广告后所占的莫斯中国科学技术大学学是稍稍?

#include
#include
#define lson rt<<1,s,mid
#define rson rt<<1|1,mid+1,e
using namespace std;

const int maxn=222222;
int tre[maxn<<2];
int h,w,n;

void pushup(int rt)
{
    tre[rt]=max(tre[rt<<1],tre[rt<<1|1]);
}

void build(int rt,int s,int e)
{
    tre[rt]=w;
    if(s==e)
        return ;
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
}

int query(int rt,int s,int e,int x)
{
    if(s==e)
    {
        tre[rt]-=x;
        return s;
    }
    int mid=(s+e)>>1;
    int ans=(tre[rt<<1]>=x)?query(lson,x):query(rson,x);
    pushup(rt);     //直接把更新操作写到query函数里。
    return ans;
}

int main()
{
    while(scanf("%d%d%d",&h,&w,&n)==3)
    {
        if(h>n) h=n;    //h>n的话,多余的就空间就浪费掉了,而且貌似会RE
        build(1,1,h);
        while(n--)
        {
            int q;
            scanf("%d",&q);
            if(tre[1]

2795 Billboard.(线段树)
标题连接: ~~~~
最初上学数据结构,从轻便的开始吧,刷题累了就写解题报告,…

HDU – 2795 – Billboard (线段树)

 

难题传送:Billboard

 

思路:有一个h*w的木板(能够看做h行,每行最多放w的上空),每一趟放1*L大小的货品,再次回到最上边能够容纳L长度的地方,未有则输出-1;

 

AC代码:

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = 200005;
int h, w, n;

int a[maxn << 2];

void build(int l, int r, int rt) { //建树,记录最大值 
 a[rt] = w;
 if(l == r) return;
 int mid = (l + r) >> 1;
 build(l, mid, rt << 1);
 build(mid + 1, r, rt << 1 | 1);
}

int query(int x, int l, int r, int rt) { //查询并更新 
 if(l == r) { //找到位置,更新并且返回当前位置 
  a[rt] -= x;
  return l;
 }
 int mid = (l + r) >> 1;
 int ret;
 if(a[rt << 1] >= x) ret = query(x, l, mid, rt << 1);
 else ret = query(x, mid + 1, r, rt << 1 | 1);
 a[rt] = max(a[rt << 1], a[rt << 1 | 1]);
 return ret;
}

int main() {
 while(scanf("%d %d %d", &h, &w, &n) != EOF) {
  if(h > n) h = n; //优化,当h比n大时用不到这么多,可以去掉多余的 
  build(1, h, 1); 
  for(int i = 0; i < n; i ++) {
   int x;
   scanf("%d", &x);
   if(a[1] < x) puts("-1");
   else printf("%d\n", query(x, 1, h, 1));//这里h写成n了,检查半天(⊙﹏⊙)b 
  }
 }
 return 0;
}

 

 

 

 

 

 

– 2795 – Billboard (线段树)
标题传送:Billboard
思路:有一个h*w的木板(能够作为h行,每行最多放w的上空),每趟放1*L大小的物料,重回…

Billboard

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

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

Author
[email protected]
Source HDOJ 2009 Summer Exercise(5)
Recommend lcy | We have carefully selected several similar problems for
you: 1698 1542 1828 1540 1255
标题大要:八个h*w的通知牌,要在其上贴布告。
输入的是1*wi的w值,那些是通告的尺码接下去要满意的尺码有:1、尽量往上,同一高度尽量靠左。2、求第n个广告所在的行数。3、未有适用的地方贴了则输出-1。
解题思路:利用线段树可以得出区间的最大值,在结构体中定义二个Max变量,用来代表这段距离内有最多空位的那一行的空位长度。与输入进去的长度进行相比,先左臂比较,再动手。(也等于左子树的最大值大于他,就询问左子树,不然查询右子树)。

详尽代码。

#include 
#include 
#include 

using namespace std;

struct node
{
    int l,r;
    int Max;//这段区间内有最多空位的那一行的空位长度
} s[200000*4];

void InitTree(int l,int r,int k,int w)
{
    s[k].l=l;
    s[k].r=r;
    s[k].Max=w;
    if (l==r)
        return ;
    int mid=(l+r)/2;
    InitTree(l,mid,2*k,w);
    InitTree(mid+1,r,2*k+1,w);
}

void UpdataTree(int ww,int k)
{
    if (s[k].l==s[k].r)
    {
        printf ("%d\n",s[k].l);
        s[k].Max-=ww;
        return ;
    }
    if (ww<=s[k*2].Max)
        UpdataTree(ww,k*2);
    else
        UpdataTree(ww,k*2+1);
    s[k].Max=s[k*2].Max>s[k*2+1].Max?s[k*2].Max:s[k*2+1].Max;
}

int main()
{
    int h,w,n;
    int ww;
    while (~scanf("%d%d%d",&h,&w,&n))
    {
        if (h>n)//h<=n,大了就没有意义了
            h=n;
        InitTree(1,h,1,w);
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&ww);
            if (s[1].Max>=ww)
                UpdataTree(ww,1);
            else
                printf ("-1\n");
        }
    }
    return 0;
}

2795 Billboard(线段树)
标题链接: Billboard Time
Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K
(Java/…

hdu 2795 Billboard(线段树)

难点链接:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 澳门新葡亰官网app 版权所有