題目鏈接：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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71874.html
標籤：其他
上一篇：資料結構&演算法