关键词：
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795
题目大意：有一个h*w的公告牌，要在其上贴公告。现在有n个公告，每个公告的尺寸为1*wi，即高度都为1，现在依次给出n个公告的宽度wi，需要求出每个公告在广告牌所在的行数。要求：对于同一个公告尽量贴在公告牌的上方，如果高度一致，尽量贴在广告牌的左侧。如果没有合适的位置，则输出-1.
例：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define maxn 200005
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define pushup() tree[root]=max(tree[root<<1],tree[root<<1|1])
int tree[maxn<<2];
int n,h,w,x;
void build(int l,int r,int root)
if(l==r)
tree[root]=w;
return;
int mid=l+r>>1;
build(lson);
build(rson);
pushup();
int query(int val,int l,int r,int root)
if(l==r)
tree[root]-=val;
return l;
int mid=l+r>>1;
int ans;
if(val<=tree[root])
if(tree[root<<1]>=val)
ans=query(val,lson);
else
ans=query(val,rson);
pushup();
return ans;
int main()
while(~scanf("%d%d%d",&h,&w,&n))
if(h>n)
h=n;
build(1,h,1);
for(int i=1;i<=n;i++)
scanf("%d",&x);
if(x>tree[1])
printf ("%d
",-1);
else
printf("%d
",query(x,1,h,1));
return 0;
hdu2795billboard线段树维护区间最大值&&查询变形(代码片段)
任意门：http://acm.hdu.edu.cn/showproblem.php?pid=2795BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):28743 &nb 查看详情
hdu2795billboard线段树(代码片段)
...区间[l,r]的最大值大于等于C我们就可以放置，所以考虑用线段树维护区间的最大值。代码如下：1#include<bits/stdc++.h>2usingnamespacestd;3typedefunsignedintui;4typedeflonglongll;5typedefunsignedlonglongull;6#definepfprintf7#definemem(a,b)memset(a,b,sizeof(a))8#d... 查看详情
hdu2795billboard（线段树）
题目链接：pid=2795">http://acm.hdu.edu.cn/showproblem.php?pid=2795BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):16673 &nbs 查看详情
hdu2795billboard(线段树)
题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=2795题目：BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):22963 查看详情
hdu2795billboard贴广告（线段树）
ProblemDescriptionAttheentrancetotheuniversity,thereisahugerectangularbillboardofsizeh*w(hisitsheightandwisitswidth).Theboardistheplacewhereallpossibleannouncementsareposted:nearestprogrammingcompetit 查看详情
hdu2795线段树单点更新
BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):23498 AcceptedSubmission(s):9687ProblemDescriptionAtt 查看详情
hdu2795billboard（线段树）
BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):15625 AcceptedSubmission(s):6580ProblemDescriptionAtt 查看详情
hdu-2795billboard（线段树）(代码片段)
...第n个广告的所在的位置，不能贴则为-1;算法思想：利用线段树可以求区间的最大值;将位置即h用来建树(h<=n,大了没有意义);树中存储的为该位置还拥有的空间;若左子树的最大值大于他,就查询左子树，否则查询右子树;#include<i... 查看详情
hdu2795billboard(线段树+贪心)(代码片段)
...时间复杂度O(n^2),无法AC.于是我们可以考虑二分的思想:用线段树维护每一行剩余的空间的大小的最大值。每次查询时，采用类似于二分答案的方法，每到达线段树的一个节点，若它的左子树最大值>=xi,则左子树中必存在合法的... 查看详情
hdu2795billboard（线段树单点更新）
BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):14337 AcceptedSubmission(s):6148ProblemDescriptionAtt 查看详情
hdu-2795billboard（线段树）
...单放在第几行，若无法放上，则输出-1。分析：二分，用线段树维护，若前半区间所有行的最大值大于等于wi，那么继续在前半区间搜索，否则搜索后半区间。#include<cstdio>#include<cstring>#include<cstdlib>#include<c 查看详情
hdu2795billboard(线段树单点更新)
BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):29637 AcceptedSubmission(s):11993 ProblemDescriptionAttheentrancetotheuniversity,thereisahugerectangularbillboardofsizeh*w(hisitsheightandwisitswidt... 查看详情
hdu2795billboard(线段树，找第一个大于w的点)
BillboardTimeLimit:20000/8000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10676 AcceptedSubmission(s):4728ProblemDescriptionAtt 查看详情
hdu2795(线段树单点更新&区间最值)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：有一个h*w的板子，要在上面贴n条1*x的广告，在贴第i条广告时要尽量将其靠上贴，并输出其最上能贴在哪个位置； 思路：可以将每行剩余空间大小存储到一个数组中，... 查看详情
hdu2795billboard(线段树单点更新&&求区间最值位置)
...都尽量选择靠上靠左的位置，那既然这样，我们以1~h建立线段树，给每一个叶子节点赋值初值w表示当前行最大能够容纳宽度为w的公告纸，那么对于某一输入wi只要在线段树的尽量靠左的区间找出能够容纳这张公告的位置（即叶 查看详情
hdu2795billboard题解(代码片段)
HDU2795Billboard线段树例题解析合集题意：有一个h行w列的矩形，在里面横放m条大小为1*l[i]的小长方形，不能重叠，如果能放得下，输出能放下的最小行数，放不下输出-1由于只有m个长方形，最多只需要m行(h范围很大)，把h对m取min... 查看详情
hdu-4819-线段树套线段树(代码片段)
...里的floor((maxv+minv)/2)并把中间的元素修改为这个值。 线段树套线段树，第一层X表示对行建立的线段树，内层表示对Y也就是列建立的线段树。 分别对X和Y建立相应的函数来完成操作，当更新X树的节点时，再更新完当前X 查看详情
hdu-1540线段树刷题(代码片段)
title:hdu-1540线段树刷题date:2018-10-1819:55:21tags:acm刷题categories:ACM-线段树概述哇，，，这道线段树的题可以说是到目前为止我所做过的最难的一道了吧QAQ，，，，，，一开始读完题就是一脸懵逼，，，，完全不知道该从哪里下手，，... 查看详情