hdu 2795 Billboard

简介: 点击打开hdu 2795 思路: 线段树+单点更新 分析: 1 题目的意思是给定一个h*w的广告牌h为高,w为宽,现在有n个高为1宽为wi的小广告要放上去,原则是最先放最上面和最左边的位置 2 题目的h和w的最大值为10^9,但是n最大为200000。

点击打开hdu 2795

思路: 线段树+单点更新

分析:

1 题目的意思是给定一个h*w的广告牌h为高,w为宽,现在有n个高为1宽为wi的小广告要放上去,原则是最先放最上面和最左边的位置

2 题目的h和w的最大值为10^9,但是n最大为200000。所以我们可以知道最多用掉的广告牌就是x = min(n , h),而这个值就是200000,所以我们可以把每一行作为一个点来利用线段树,线段树的区间[i , j]存储的是第i行到第j行的最大的剩余空间,那么我们只要每一次去查找整个区间[1 , x] ,然后我们要优先的考虑左子树,这样就能够满足要求的条件了


代码;

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-09-02                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define Lson(x) (x<<1)
#define Rson(x) (Lson(x)|1)
#define Mid(x,y) ((x+y)>>1)
#define Sum(x,y) (x+y)

typedef long long int64;
const int MAXN = 200010;

int h , w , n;
struct Node{
    int left;
    int right;
    int64 maxVal;
};
Node node[4*MAXN];

void push_up(int pos){
    node[pos].maxVal = max(node[Lson(pos)].maxVal , node[Rson(pos)].maxVal);
}

void init(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    if(node[pos].left == node[pos].right){
        node[pos].maxVal = w;
        return;
    }
    int mid = Mid(left , right);
    init(left , mid , Lson(pos));
    init(mid+1 , right , Rson(pos));
    push_up(pos);
}

void update(int index , int val , int pos){
    if(node[pos].left == node[pos].right){
        node[pos].maxVal -= val;
        return;
    }
    int mid = Mid(node[pos].left , node[pos].right);
    if(index <= mid) 
        update(index , val , Lson(pos));
    else
        update(index , val , Rson(pos));
    push_up(pos);
}

int query(int left , int right , int val , int pos){
    if(node[pos].maxVal < val)
        return -1;
    if(left == right)
        return node[pos].maxVal >= val ? left : -1;
    int mid = Mid(left , right);
    int ans = query(left , mid , val , Lson(pos));
    if(ans == -1)
        return query(mid+1 , right , val , Rson(pos));
    else
        return ans;
}

void input(){
    int m = n;
    int i , x;
    n = min(n , h);
    init(1 , n , 1);
    while(m--){
        scanf("%d" , &x);
        int ans = query(1 , n , x , 1);
        printf("%d\n" , ans);
        if(ans != -1)
           update(ans , x , 1);
    }
}

int main(){
    while(scanf("%d%d%d" , &h , &w , &n) != EOF)
        input();
    return 0;
}



目录
相关文章
|
7月前
|
Java
HDU-1896-Stones
HDU-1896-Stones
30 0
|
C++ Java
HDU1880
题意就是根据咒语查功能,根据功能查看是否存在相应咒语,题意简单,不过是道不错的练习题。         下面的都MLE了,听说C++用G++提交才可以AC,否则也MLE;方法很多,不想做了……         方法一:我用Java的HashMap一直MLE,即便由value反查key减少映射数也一样MLE,听说C++的map可以AC。
1085 0
hdu 1856 More is better
点击hdu 1856思路: 思路: 离散化+并查集 分析: 1 点数最多为10^7,但是边数最多10^5,所以我们必须采用离散化,然后利用带权并查集的思想,rank[x]表示的是以x为根节点的集合的元素个数 2 这一题主要注意的就是当...
830 0