本文共 1490 字，大约阅读时间需要 4 分钟。
题目链接：
思路：h = 1e9行不通，因为广告是1*w的，所以n个广告最多只需要 h = n的高度，那么h=2e5就可以接受了。
用树状数组维护区间最大值。
从前往后区间查询哪一大块块首先满足条件，然后一直缩小区间，直到区间长度等于1，输出答案，然后修改该点可用的w，
再修改区间最大值。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std;13 #define ll long long14 #define pb push_back15 #define fi first16 #define se second17 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 }
转载地址：http://xyuki.baihongyu.com/