题目链接:https://vjudge.net/problem/HDU-2795
思路:h = 1e9行不通,因为广告是1*w的,所以n个广告最多只需要 h = n的高度,那么h=2e5就可以接受了。
用树状数组维护区间最大值。
从前往后区间查询哪一大块块首先满足条件,然后一直缩小区间,直到区间长度等于1,输出答案,然后修改该点可用的w,
再修改区间最大值。
1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 #include <queue> 5 #include <string> 6 #include <stack> 7 #include <vector> 8 #include <list> 9 #include <cstdio> 10 #include <cstring> 11 #include <cmath> 12 using namespace std; 13 #define ll long long 14 #define pb push_back 15 #define fi first 16 #define se second 17 18 const int N = 2e5+10; 19 int a[N],c[N]; 20 int n,h,w; 21 22 inline int lb(int x){ 23 return x&(-x); 24 } 25 26 void update(int inx){ 27 for(int i = inx; i <= h; i += lb(i)){ 28 c[i] = a[i]; 29 int d = lb(i); 30 if(d == 1) continue; 31 for(int j = 1; j < d; j <<= 1) 32 c[i] = max(c[i], c[i-j]); 33 } 34 } 35 36 inline bool fun(int& l,int& r,int it){ 37 while(r <= h){ 38 // cout << "fun" << endl; 39 if(c[r] < it){ 40 l = r; 41 r += lb(r); 42 if(r > h) r = l+1;//要遍历所有的分块区间 43 } 44 else return 1; 45 } 46 return 0; 47 } 48 49 void solve(){ 50 while(~scanf("%d%d%d",&h,&w,&n)){ 51 h = h >= n ? n : h; 52 for(int i = 1; i <= h; ++i) a[i] = c[i] = w;//初始化 53 int it; 54 for(int p = 1; p <= n; ++p){ 55 scanf("%d",&it); 56 int l = 1,r = 1,ok = 0; 57 while(fun(l,r,it)){//找是否有满足的区间 58 // cout << "main" << endl; 59 ok = 1; 60 if(l == r){ 61 printf("%d\n",l); 62 a[l] -= it; 63 update(l); 64 break; 65 } 66 else r = ++l;//缩小区间 67 } 68 if(!ok) printf("-1\n"); 69 } 70 } 71 } 72 73 int main(){ 74 75 // ios::sync_with_stdio(false); 76 // cin.tie(0); cout.tie(0); 77 solve(); 78 79 return 0; 80 }
Billboard HDU - 2795(树状数组,单点修改,区间查询)
原文:https://www.cnblogs.com/SSummerZzz/p/12526552.html