HDU2795-Billboard(线段树)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795

题意：给你一个高为h，宽为w的板子，以及n个高为1，宽度为wi的公告，如果板子能放下这个公告的话，尽可能将这个公告往上往左放，公告只能横着贴，贴在一行里，如果放不下就输出-1，如果放得下，就输出在板子上所放置的公告的高度（也就是行数）。

思路：将板子每个高度的宽度设为线段树叶子节点的值（也就是说叶子节点的值代表每行的空位的个数），将线段树存放区间和的数组sum[]的值用来表示其两个儿子节点之间的最大值（目的在于引导搜寻的方向），在线段树的递归过程中，总是先往左边递归，也就是说，会先往上方进行寻找，如果左右节点的空位都满足的话，会优先往左边搜寻，直到到达叶子节点，说明已经搜到了能放下这个公告的行数，将此行的值减去这个公告的宽度，输出所在行数，结束递归，同时更新区间和的值。

值得注意的是，此题的高度是10^9，以10^9建立数组会爆内存，但是题目中给出的公告的数量是2^5，每个公告都有确定的宽度，如果一行放不下的话就都放不下，如果能放得下的话，每个公告最多占一行，所以说板子的高度只要有2^5就足够了，在板子的高度超过2^5的时候，只需要让板子的高度为n就ok了，没超过2^5的时候，就照题目来。

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include<set>
  8 #include
  9 #include
 10 #include
 11 #include<string>
 12 #define ll long long
 13 #define ull unsigned long long
 14 #define inf 0x3f3f3f3f
 15 #define inff 0x7fffffff
 16 using namespace std;
 17 const int N = 200000 + 10;
 18 const int M = 1000000 + 10;
 19 const ll mod = 1e9 + 7;
 20 
 21 ll a[N], wi[N];
 22 ll sum[N << 2];
 23 //mapmp;
 24 int flag = 1;
 25 
 26 void PushUp(int rt) {
 27     sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
 28 }
 29 
 30 void Build(int l, int r, int rt) {
 31 
 32     if (l == r) {
 33         sum[rt] = a[l];
 34         //mp[rt] = l;
 35         return;
 36     }
 37     int mid = (l + r) >> 1;
 38     Build(l, mid, rt << 1);
 39     Build(mid + 1, r, rt << 1 | 1);
 40     PushUp(rt);
 41 
 42     return;
 43 }
 44 
 45 void PointUpdate(ll L, int l, int r, int rt) {
 46 
 47     if (l == r) {
 48         //flag = 0;
 49         sum[rt] -= L;
 50         /*if (sum[rt] < 0) {
 51             sum[rt] += L;
 52             cout << -1 << "\n";
 53         }*/
 54         cout << l << "\n";
 55         return;
 56     }
 57     int mid = (l + r) >> 1;
 58     if (L <= sum[rt << 1]) PointUpdate(L, l, mid, rt << 1);
 59     else if (L <= sum[rt << 1 | 1]) PointUpdate(L, mid + 1, r, rt << 1 | 1);
 60     else {
 61         cout << -1 << "\n";
 62         return;
 63     }
 64     PushUp(rt);
 65 
 66     return;
 67 }
 68 
 69 //ll Query(int L, int R, int l, int r, int rt) {
 70 //    
 71 //    if (l >= L && r <= R) {
 72 //        return sum[rt];
 73 //    }
 74 //    int mid = (l + r) >> 1;
 75 //
 76 //    ll ans = 1;
 77 //    if (L <= mid) ans = (ans * Query(L, R, l, mid, rt << 1)) % mod;
 78 //    if (R > mid) ans = (ans * Query(L, R, mid + 1, r, rt << 1 | 1)) % mod;
 79 //    //PushUp(rt);
 80 //
 81 //    return ans;
 82 //}
 83 
 84 int main() {
 85 
 86     ios::sync_with_stdio(false);
 87     cin.tie(0);
 88     int h, w, n;
 89     while (cin >> h >> w >> n) {
 90         for (int i = 1; i <= n; i++) {
 91             cin >> wi[i];
 92         }
 93         if (h > 200000) {
 94             for (int i = 1; i <= n; i++) {
 95                 a[i] = w;
 96             }
 97             Build(1, n, 1);
 98             for (int i = 1; i <= n; i++) {
 99                 //flag = 1;
100                 PointUpdate(wi[i], 1, n, 1);
101                 //if (flag) cout << -1 << "\n";
102             }
103         }
104         else {
105             for (int i = 1; i <= h; i++) {
106                 a[i] = w;
107             }
108             Build(1, h, 1);
109             for (int i = 1; i <= n; i++) {
110                 //flag = 1;
111                 PointUpdate(wi[i], 1, h, 1);
112                 //if (flag) cout << -1 << "\n";
113             }
114         }
115         /*for (int i = 1; i <= 5; i++) cout << sum[i] << " ";
116         cout << "\n";*/
117         /*for (int i = 1; i <= n; i++) {
118             flag = 1;
119             PointUpdate(wi[i], 1, n, 1);
120             if (flag) cout << -1 << "\n";
121         }*/
122     }
123 
124     return 0;
125 }
 
线段树

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签