首页 > 代码库 > 【HDU2795】Billboard(线段树)
【HDU2795】Billboard(线段树)
大意:给一个h*w的格子,然后给出多个1*w的板子往格子里面填,如果有空间尽量往上一行填满,输出行数,无法填补,则输出-1;
可以使用线段树转化问题,将每一排的格子数目放到每一个叶子节点上,然后每有一块板子,进行query查询靠左子树的第一个大于板子的叶子,进行update操作更新叶子。每个节点附权值max叶子节点即可。令一个小坑是h和w的范围是1e9,数组太大。试想如果格子高度h > 板子的个数n,那么我们只需要压缩格子到n个高度即可。所有给叶子节点的存储空间就能压缩成n的范围即1e6。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <numeric> 9 #include <climits>10 #include <vector>11 #include <string>12 using namespace std;13 14 const int maxn = 200000 + 10;15 int maxv[maxn << 2];16 17 void PushUp (int rt) {18 maxv[rt] = max (maxv[rt * 2], maxv[rt * 2 + 1] );19 }20 21 void build (int w, int l, int r, int rt) {22 maxv[rt] = w;23 if (l == r) {24 return ;25 }26 int m = (l + r) / 2;27 build (w, l, m, rt * 2);28 build (w, m + 1, r, rt * 2 + 1);29 }30 31 int query (int x, int l, int r, int rt) {32 if (r == l) {33 maxv[rt] -= x;34 return l;35 }36 int m = (l + r) / 2;37 int ret;38 if (maxv[rt * 2] >= x) {39 ret = query (x, l, m, rt * 2);40 } else {41 ret = query (x, m + 1, r, rt * 2 + 1);42 }43 PushUp(rt);44 return ret;45 }46 47 int main () {48 int h, w, n;49 50 while (~scanf ("%d %d %d", &h, &w, &n)) {51 if (h > n) {52 h = n;53 }54 build (w, 1, h, 1);55 while (n --) {56 int x; scanf ("%d", &x);57 if (maxv[1] < x) {58 printf ("%d\n", -1);59 } else {60 printf ("%d\n", query (x, 1, h, 1));61 }62 }63 }64 return 0;65 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。