Billboard 题解 hdu2795

灰太狼 2021-10-19 04:36 335阅读 0赞

# Billboard 题解 hdu2795 #

## 题意 ##

有个广告牌，上面需要依次贴广告，广告的高度均为1，但是宽度不同，每次都想贴在最靠左上的位置，按照顺序进行广告的话，输出每个广告位于广告牌的高度。

## 解题思路 ##

使用线段树，来维护区间最大值，这样我们每次查找的时候都先判断上面点的最大值是不是大于广告的宽度，根据题意大于就先判断左节点，左节点不行再右节点，然后找到具体的点。如果小于的话，那个这个节点和他下面的节点就都不行了。

下面代码，基本上就是线段树的模板，就是维护区间的最大值这个是重点。

## 代码实现 ##

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=2e5+7; int a[maxn<<2]; int h, w, n, ans; void up(int rt) { a[rt]=max(a[rt<<1], a[rt<<1|1]); } void update(int rt, int l, int r, int x) { if(l==r){ a[rt]-=x;//表示在高度为rt处，贴完广告后剩下的宽度 ans=l; return; } int mid=(l+r)>>1; if(a[rt<<1] >= x) update(rt<<1, l, mid, x); //先看左节点是否可以 else update(rt<<1|1, mid+1, r, x); up(rt); //记得更新当前节点的最大值 } int main() { while(scanf("%d%d%d", &h, &w, &n)!=EOF) { int R=min(h,n); for(int i=1; i<=(R<<2); i++) { a[i]=w; //这里相当于建立线段树，因为开始肯定都是宽度w了 } int wi; for(int i=1; i<=n; i++) { scanf("%d", &wi); if(a[1] < wi) printf("-1\n");//a[1]维护的是整个区间的最大值，这个如果都不满足的话，就可以输出-1了。 else { update(1, 1, R, wi); printf("%d\n", ans); } } } return 0; }

转载于:https://www.cnblogs.com/alking1001/p/11316608.html

发表评论取消回复

表情：

评论列表（有 0 条评论，335人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 刷题个人题解

hdu 刷题个人题解 * 模拟 * 并查集 * dp * 数论 * 数学+规律 * BFS * 最小生成树 * 水题模拟 [...

向右看齐/ 2024年04月17日 05:32/ 0 赞/ 66 阅读

相关 HDU 2795 Billboard （线段树）

Billboard Problem Description At the entrance to the university, there is a hug

不念不忘少年蓝@/ 2024年02月17日 21:09/ 0 赞/ 27 阅读

相关 hdu 刷题个人题解

hdu 刷题个人题解模拟排序并查集 dp 数论数学+规律 BFS 图最小生成树水题模拟

约定不等于承诺〃/ 2023年07月12日 05:16/ 0 赞/ 22 阅读

相关 HDU 2795 Billboard //线段树简单应用

Billboard Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/O

朴灿烈づ我的快乐病毒、/ 2022年09月21日 00:28/ 0 赞/ 155 阅读

相关 ZOJ 2795-Ambiguous permutations

ZOJ Problem Set - 2795 Ambiguous permutations -------------------- Time Limit: 10 Sec

妖狐艹你老母/ 2022年08月20日 13:23/ 0 赞/ 14 阅读

相关 Billboard技术浅析

<table style="font-family:STHeiti"> <tbody> <tr> <td colspan="3"> <div>

比眉伴天荒/ 2022年06月13日 13:56/ 0 赞/ 301 阅读

相关 hdu-2795-Billboard(线段树)

Billboard At the entrance to the university, there is a huge rec

水深无声/ 2022年06月12日 14:16/ 0 赞/ 203 阅读

相关 Billboard 题解 hdu2795

Billboard 题解 hdu2795 题意有个广告牌，上面需要依次贴广告，广告的高度均为1，但是宽度不同，每次都想贴在最靠左上的位置，按照顺序进行广告的话，输

灰太狼/ 2021年10月19日 04:36/ 0 赞/ 336 阅读

相关 HDU 1372 Knight Moves 题解

Knight Moves Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

本是古典何须时尚/ 2021年09月20日 08:08/ 0 赞/ 254 阅读

相关 HDU - 2111 - Saving HDU【贪心】题解

目录 1.题目 2.代码 1.题目话说上回讲到海东集团面临内外交困，公司的元老也只剩下XHD夫妇二人了。显

红太狼/ 2021年07月24日 12:39/ 0 赞/ 423 阅读