首页 > 代码库 > HDU 2795 Billboard

HDU 2795 Billboard

2024-07-17 14:42:38   218人阅读

可以用线段树写。

虽然有h(1<=h<=10^9)行，但是实际用到的不会超过n(1<=n<=200000)行。  注意n>h的情况。

线段树保存区间剩余的空间最大值，每次询问+处理同时进行，优先选择左边。

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5  6 const int maxn = 200005 ; 7  8 int ma[maxn*5]; 9     int h,w,n;10 11 void maintain (int o){12     int lc=o<<1,rc=(o<<1)+1;13     ma[o]=max(ma[lc],ma[rc]);14 }15 16 int query (int o,int l,int r,int x){17     int lc=o<<1,rc=(o<<1)+1;18     int m=l+(r-l)/2;19     if (ma[o]<x||l>h)20         return -1;21     if (l==r){//cout<<ma[o]<<" "<<o<<" "<<l<<" "<<r<<endl;22         ma[o]-=x;23         return l;24     }25     else {26         int ans;27         if (ma[lc]>=x) ans=query (lc,l,m,x);28         else ans=query (rc,m+1,r,x);29         maintain (o);30         return ans;31     }32 }33 34 int main (){35     while (~scanf ("%d%d%d",&h,&w,&n)){36         for (int i=1;i<=5*n;i++)37             ma[i]=w;38         for (int i=1;i<=n;i++){39             int x;40             scanf ("%d",&x);41             int ans;42             ans=query (1,1,n,x);43             printf ("%d\n",ans);44         }45     }46     return 0;47 }

 


联系
我们