题意是给你一个h*w的广告板，然后有n张1*wi的广告要贴上去，要求尽可能的左，相同的情况下尽可能靠上。
我们可以按照层数来建立线段树，然后每一部分记录最大的w值。
#include #include #include #include #include #include #include #include #define LL(x) (x<<1) #define RR(x) ((x<<1)|1) using namespace std; const int INF=999999999; const int maxn=222222; int h,w; int Max[maxn<<2]; void build(int o,int L,int R) { Max[o]=w; if(L==R) return; int M=(L+R)/2; build(o*2,L,M); build(o*2+1,M+1,R); } int query(int o,int L,int R,int num) { if(L==R) { Max[o]-=num; return L; } int M=(L+R)/2,ans; if(Max[o*2]>=num) ans=query(o*2,L,M,num); else ans=query(o*2+1,M+1,R,num); Max[o]=max(Max[o*2],Max[o*2+1]); return ans; } int main() { int n,m; while(scanf("%d%d",&h,&w)!=EOF) { scanf("%d",&n); if(h>n) h=n; build(1,1,h); while(n--) { scanf("%d",&m); if(Max[1]