HDU2795 Billboard（线段树）
source link: https://arminli.com/hdu2795/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
HDU2795 Billboard（线段树）
March 05, 2016
题意：高为 h，宽为 w 的广告板，往上面贴一些宽都是 1 的广告。要求尽量往上和往左贴，输入能贴在第几行，如果都贴不上输出-1.
首先取 min（h，n）作为线段树长度，因为最坏情况是 n 个广告每个一行，如果 h>n 的话剩下的肯定贴不了。
用线段树来维护 1~h 中剩余长度的最大值，利用其由上而下搜索和先遍历左子树的特性，找到广告板上最上面符合条件的行数。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 200005;
int tree[maxn<<2];
int h, w, n;
void pushUp(int rt){
tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);
}
void build(int l, int r, int rt){
if(l == r){
tree[rt] = w;
return;
}
int m = l+(r-l)/2;
build(lson);
build(rson);
pushUp(rt);
}
int query(int num, int l, int r, int rt){
if(l == r){
tree[rt] -= num;
return l;
}
int ans;
int m = l+(r-l)/2;
if(tree[rt<<1] >= num)
ans = query(num, lson);
else
ans = query(num, rson);
pushUp(rt); //更新
return ans;
}
int main(){
//freopen("a.txt", "r", stdin);
while(~scanf("%d %d %d", &h, &w, &n)){
h = min(h, n);
build(1, h, 1);
for(int i = 0; i < n; i++){
int a;
scanf("%d", &a);
if(tree[1] < a) cout << "-1" << endl;
else{
cout << query(a, 1, h, 1) << endl;
}
}
}
return 0;
}
Recommend
-
25
前一阵子朋友换工作，去了新公司的一个基础服务的部门。对数据结构和算法的要求着实不低，不是平常的CRUD，而是通过各种巧妙的数据结构去完成对应的业务需求。我发现是时候夯实一下基础了，这次来看...
-
33
目录 为什么要使用线段树？ 最经典的线段树问题：区间染色 有一面墙 ，长度为n，每次选择一段儿墙进行染色，m次操作后，我们可以看见多少种颜色？
-
44
点击关注上方“ 五分钟学算法 ”， 设为“置顶或星标”，第一时间送达干货。 来源...
-
37
学习了一周的线段树和树状数组，深深地体会到了这每种操作几乎都是 \(O(logN)\) 级别的数据结构的美，但是做起题来还是相当痛苦的（特别是一开始只会模板的时候，很难灵活运用线段树的性质）。还好有雨巨大神带入门，视频讲...
-
33
题目描述 “南山之首日鹊山。其首日招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名日祝余，食之不饥……又东三百里，日堂庭之山，多棪木，多白猿，多水玉，多黄金。 又东三百八十里，日猨翼之山，其...
-
23
大家好，欢迎阅读周三 算法数据结构 专题，今天我们来聊聊一个新的数据结构，叫做线段树。 线段树这个数据结构很多人可能会有点蒙，觉得没有听说过，但是它非常非常有名，尤其是在竞赛圈，可以说是 竞赛圈的必备技能
-
10
两个线段相交测试 两个线段相交测试 [TOC] 因为需要用到线段相交测试，找了一个不错的实现，改成了c++的 把参考[1]中的代码用c++翻译了一下，几乎都不用改，放在github上了[5]...
-
11
线段树笔记 有这样一类问题，给定一个数列，让你求某段区间内和。如果对某个值或某段区间内的值进行修改后，如何快速的求和。如果线性执行更新操作或求和操作，无疑时间复杂度太大了。那么借助分治的思想，在执行更新区间...
-
9
线段树 (区间树)Table of Contents不查不知道，一查吓一跳，“线段树”这个名字的定义真是混乱到一定程度了。 维基百科 Segment Tree 说它是一种数据结构，用来...
-
16
WPF 基础 2D 图形学知识 判断点是否在线段上在知道一个使用两个点表示的线段，和另一个点，求另一个点是否在线段上 本文算法属于通用的算法，可以在 WPF 和 UWP 和 Xamarin 等上运行，基本上所有的 .NET 平台都能执行 如下图，如果...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK