点击打开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;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
自己做的HDU ACM已经AC的题目
HDU图论题目分类