[HDU] 2795 Billboard [线段树区间求最值]
Billboard
Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11861 Accepted Submission(s): 5223
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.
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.
题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
思路:每次找到最大值的位子,然后减去L
线段树功能:query:区间求最大值的位子
#include<cstdio>
#include<string.h>
#include<algorithm> #define clr(x,y) memset(x,y,sizeof(x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 const int N=2e5+;
using namespace std; int h,w,n,MAX[N<<]; void PushUp(int rt)
{
MAX[rt]=max(MAX[rt<<],MAX[rt<<|]);
} void build(int l,int r,int rt)
{
int m; MAX[rt]=w;
if(l==r) {
return;
} m=(l+r)>>;
build(lson);
build(rson);
} int query(int x,int l,int r,int rt)
{
int m,ret;
if(l==r) {
MAX[rt]-=x;
return l;
}
m=(l+r)>>;
ret=(MAX[rt<<]>=x) ? query(x,lson) : query(x,rson);
PushUp(rt);
return ret;
} int main()
{
int x;
while(~scanf("%d%d%d",&h,&w,&n)) {
if(h>n) h=n;
build(,h,);
while(n--) {
scanf("%d",&x);
if(MAX[]<x) puts("-1");
else printf("%d\n",query(x,,h,)); } } return ;
}
最新文章
- Android-修改TabWidget字体大小颜色及对齐
- 核心动画 (CAAnimationGroup)
- Unix环境编程之定时、信号与中断
- POJ 1773 Parity game 带权并查集
- sublime工具 插件自动补全方法
- ThreadPool.QueueUserWorkItem的性能问题
- Delete和Truncate的区别
- circularprogressbar/smoothprogressbar开源视图使用学习
- PHP新手之学习类与对象(2)
- Ubuntu热键控制spotify播放和音量调节
- 一篇文章带你了解Cloud Native
- 《Systems Performance》阅读笔记及收获
- 【Docker】(2)---仓库、镜像、容器
- 【20190228】JavaScript-获取子元素
- Appium 学习三:Appium-Desktop 填坑
- 【Spring Security】二、数据库管理用户权限
- mysql基本知识总结
- ASP.NET MVC学习(一)之路由篇Route
- CSS-下拉导航条
- 【转】细说UI线程和Windows消息队列
热门文章
- CCI_chapter 16 Low level
- 使用QtScript库解析Json数组例子
- 必须用C模拟OS?
- http与https的区别以及https的加密原理
- 从有限状态机的角度去理解Knuth-Morris-Pratt Algorithm(又叫KMP算法)
- scp 对拷文件夹 和 文件夹下的所有文件 对拷文件并重命名
- hibernate 对 sql server 2005 分页改进
- Android——LayoutInflater详解
- C++内存泄露检測原理
- 1042. Shuffling Machine (20) - sstream实现数字转字符串