题意：有一块长方形的广告板，往上面贴广告，然后给n个1*wi的广告，要求把广告贴上去，如果前面的行可以贴，就要贴前面的并且要靠左贴，前面的贴不下就贴在下面，
广告的高度是wi，如果能贴在上面输出最小的高度，如果不能就输出-1。
解题思路：如果以行数为区间，建立线段树，他给的h有10^9次，是创不了10^9这么大的数组的。然而我们知道给定N个广告，应为宽度一定，那么最高也不会超过N；只是我们可以开4×N为数组来建树；我把最后树的叶子节点表示广告牌的高度，并且左边的高度小于右边的；而父节点存储子节点的最大剩余值，如果最大值都比wi都小，则表示该节点不可能贴上广告，那么我们就要回朔到上一个节点，也就是下层；这就是该题的思路；
注意：当我们找到指定的层数是我们就要直接终止继续回朔，我们可以用个全局变量标记。
#include#include #include using namespace std; class Node { public: int max,l,r,mid,floor; }; Node tree[800024]; int flag,floor1; class Tree { public: void Maketree( int l,int r,int cnt ,int& floor,int length); void research( int cnt,int width ); int Max( int a,int b ) { return a>b?a:b; } }; void Tree::Maketree( int l, int r ,int cnt , int& floor ,int length) { if( l==r ) { tree[cnt].l = tree[cnt].r =tree[cnt].mid=l; tree[cnt].max = length; tree[cnt].floor = floor; floor++; return; } else { tree[cnt].l = l; tree[cnt].r = r; tree[cnt].mid = ( l+r )>>1; tree[cnt].floor = 0; Maketree( l , tree[cnt].mid , cnt*2 , floor , length ); Maketree( tree[cnt].mid + 1 , r ,cnt*2+1, floor , length ); tree[cnt].max = Max( tree[cnt*2].max ,tree[cnt*2+1].max ); } } void Tree::research( int cnt ,int width) { if( flag==1 ) { tree[cnt].max = Max( tree[cnt*2].max,tree[cnt*2+1].max ); return ; } if( tree[cnt].max>=width) { if( tree[cnt].floor>0 ) { flag=1; tree[cnt].max -= width; floor1=tree[cnt].floor; return ; } else { research( cnt*2,width ); if( flag==1 ) { tree[cnt].max = Max( tree[cnt*2].max,tree[cnt*2+1].max ); return ; } research( cnt*2+1,width ); if( flag==1 ) { tree[cnt].max = Max( tree[cnt*2].max,tree[cnt*2+1].max ); return ; } } } } int main( ) { int h,w,n; while( scanf( "%d%d%d",&h,&w,&n )==3 ) { Tree e; int floor = 1; if( n<=h ) e.Maketree( 1,n,1,floor,w ); else e.Maketree( 1,h,1,floor,w ); while( n-- ) { floor1=-1; flag=0; scanf( "%d",&w ); e.research( 1,w ); printf( "%d\n",floor1 ); } } return 0; }