hdu2795 Billboard(线段树)
2024-10-18 23:22:45
题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
思路:每次找到最大值的位子,然后减去L
线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)
#include<stdio.h>
#include<algorithm>
using namespace std; #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = ;
int MAX[maxn<<];
int h,w,n;
void PushUP(int rt)
{
MAX[rt]=max(MAX[rt<<],MAX[rt<<|]);
}
///这里与前面的不一样
void build(int l,int r,int rt)
{ ///每一个的开始都是W;
MAX[rt]=w;
if(l==r)
{
return ;
}
int m=(r+l)>>;
build(lson);
build(rson); } int query(int x,int l,int r,int rt)
{
int ret;
if( l==r )
{
MAX[rt]-=x;
return l;
}
int m=(l+r)>>;
if(MAX[rt<<]>=x)
ret=query(x,lson);
else
ret=query(x,rson);
PushUP(rt);
return ret;
}
int main( )
{ while(scanf("%d%d%d",&h,&w,&n)!=EOF)
{
if(h>n)
h=n;
build(,h,);
while(n--)
{
int x;
scanf("%d",&x);
if(MAX[]<x)
puts("-1");
else
printf("%d\n",query(x,,h,));
}
}
return ;
}
最新文章
- 从零开始编写自己的C#框架(5)——三层架构介绍
- jquery层级原则器(匹配父元素下的子元素)
- HDU5772 String problem 最大权闭合图+巧妙建图
- MySQL基础学习之数据库
- 微信jssdk批量展示卡包中的卡券
- Hadoop在Windows下的安装配置
- 关于DB2死锁处理
- Extjs 4.0 Window
- Vue.js-08:第八章 - 组件的基础知识
- MySQL数据库聚合函数
- Froms 认证 二级域名共享session登录凭证
- 使用eclipse粗略统计代码代数【原】
- mysql中外键的创建与删除
- echarts饼图配置
- 哪个先执行:@PostConstruct和@Bean的initMethod?
- 013-- mysql常用的查询优化方法
- The YubiKey NEO
- python的一些科学计算的包
- Latex 学习之旅
- [Grunt + AngularJS] Using ng-annotate for min-safe AngularJS
热门文章
- 【转】Xcode 清理存储空间
- 2018网络预选赛 徐州H 线段树+树状数组
- javascript使用setTimeout、setInterval时找不到变量的问题
- 服务机器人的小脑——SLAM技术
- 用fontcreator创建了一个半成品的字体
- JavaPersistenceWithHibernate第二版笔记-第六章-Mapping inheritance-005Table per subclass with joins(@Inheritance(strategy = InheritanceType.JOINED)、@PrimaryKeyJoinColumn、)
- ZROI2018普转提day2t4
- Luogu 2824 [HEOI2016/TJOI2016]排序
- Entity Framework Tutorial Basics(4):Setup Entity Framework Environment
- jQuery 事件 - trigger() 方法