博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 2795 Billboard
阅读量:6272 次
发布时间:2019-06-22

本文共 1608 字,大约阅读时间需要 5 分钟。

线段树

题意:有一个长H宽W的板,上面贴纸条,纸条都是长1宽w的,贴纸条的原则是,不能覆盖或重叠别人的纸条,尽量往上贴,进而尽量往左贴

第一行3个数字,H,W,N,N表示有N个纸条,下面n行每行一个数字,表示每个纸条的宽,每个输入对应一个输出,就是这个纸条放在哪一行,如果没地方放它就输出-1

数据很大,不过是纸老虎,因为H=min(H,N),这个很容易理解,行数多了也用不上。

 

/*h=min(h,Q);线段树区间长度为h,每个叶子a[i]表示第i行剩下的长度,一开始都是w对于每个询问,我们其实是将长度为l的长条放入一行呢,即对应放到a数组的一位里,要满足a[i]>=l,并且最靠左所以问题转化为在a数组最左端找一个a[i]>=l所以对于线段树,我们记录一个信息,在这个区间内,叶子的最大值对于当前要查询的宽度和当期节点,若左孩子最大值>=查询宽度则去到左孩子,否则去到右孩子查询解决于叶子节点,然后从叶子返回,返回时就顺便更新路径中节点的最大值,查询和更新合为一体所以只写了一个函数感觉可以优化,记录标号什么的,但是不去实现了*/#include 
#include
#include
#define N 1000000010#define M 200010#define INF 0x3f3f3f3f#define min(a,b) ((a)<(b)?(a):(b))#define max(a,b) ((a)>(b)?(a):(b))#define lch(i) ((i)<<1)#define rch(i) ((i)<<1|1)int H,W,Q;struct node{ int l,r; int max; int mid() { return (l+r)>>1; }}t[4*M];void build(int l , int r ,int rt){ t[rt].l=l; t[rt].r=r; t[rt].max=W; if(l==r) return ; int mid=t[rt].mid(); build(l,mid,lch(rt)); build(mid+1,r,rch(rt));}int query(int w ,int rt){ if(t[rt].l == t[rt].r) { t[rt].max -= w; return t[rt].l; } int index; if(t[lch(rt)].max >= w) index = query(w,lch(rt)); else index = query(w,rch(rt)); t[rt].max = max(t[lch(rt)].max , t[rch(rt)].max); return index;}int main(){ while(scanf("%d%d%d",&H,&W,&Q)!=EOF) { H=min(H,Q); build(1,H,1); for(int i=1; i<=Q; i++) { int w; scanf("%d",&w); if(t[1].max < w) { printf("-1\n"); continue; } int index = query(w,1); printf("%d\n",index); } } return 0;}

 

转载地址:http://jlopa.baihongyu.com/

你可能感兴趣的文章
Threejs 官网 - Three.js 的图形用户界面工具(GUI Tools with Three.js)
查看>>
Atitit.Java exe bat 作为windows系统服务程序运行
查看>>
session的生命周期
查看>>
数据库的本质、概念及其应用实践(二)
查看>>
iOS开发多线程--(NSOperation/Queue)
查看>>
php的ajax简单实例
查看>>
maven常用构建命令
查看>>
C#:关联程序和文件
查看>>
推荐科研软件
查看>>
gradle
查看>>
如何取消未知类型文件默认用记事本打开
查看>>
[Javascript] Immute Object
查看>>
Java 关于finally、static
查看>>
Posix mq和SystemV mq区别
查看>>
P6 EPPM Manual Installation Guide (Oracle Database)
查看>>
XMPP协议、IM、客户端互联详解
查看>>
PHP写文件函数
查看>>
mysql的sql_mode合理设置
查看>>
函数连续性与可导性
查看>>
linux下libevent安装
查看>>