hdu 2795

题意：一块h*w的广告板上贴广告，每条广告均为1*wi；
如果能贴，输出贴的位置（即第几行，位置尽量靠上，靠左）；否则输出-1.

其实也就是区间最值的维护，该区间，最大空间为多少，是否能将某广告贴上，直接在查询时维护

代码如下：

/*
题意：一块h*w的广告板上贴广告，每条广告均为1*wi；
如果能贴，输出贴的位置（即第几行，位置尽量靠上，靠左）；否则输出-1.
*/
// hdu 2795
#include <iostream>
#include <cstdio>
#define MAX 200005
using namespace std;

typedef struct node
{
  int s,e;
  int w;
  node (int a=0,int b=0,int c=0):s(a),e(b),w(c){}
}node;

 node tree[MAX<<3];
 int h,w,n;
 int flag =0;
 
 int Max (const int & a,const int & b)
 {
     if (a > b) return a;
     else return b;
 }
 
void build(int T,int s,int e)
{
  if (s==e)
  {
      tree[T] = node(s,e,w);
  }
  else
  {
      int mid = (s+e)>>1;
      build(T<<1,s,mid);
      build (T<<1|1,mid+1,e);
      tree[T] = node(s,e,w);
  }
}

//其实就是在能放得下的情况下，先找左子树，在找右子树，总能找到合适的位置，然后返回所处的行
int Query(int T,int sb)
{
  if (tree[T].w < sb) return 0;//该区间不可能存在答案了 
  if (tree[T].s== tree[T].e)
  {
           tree[T].w-=sb;
           return tree[T].s;
  }
   //先查找左子树 
  int s1 = Query(T<<1,sb);
  if (!s1)//左边没找到 
  {
      //去右边找 ,并且一定在右边 
         s1 = Query(T<<1|1,sb);
  }
  tree[T].w = Max (tree[T<<1].w ,tree[T<<1|1].w);
  return s1;
}

int main ()
{
   //std::ios::sync_with_stdio(false);
   int sb;
   while(~scanf("%d%d%d",&h,&w,&n)) //在这里我只想说该死的cin cout  
   {   if (h>n) h=n;
          build(1,1,h);
     for (int i=0;i<n;++i)
      {
            scanf ("%d",&sb);
            if (tree[1].w<sb) printf ("-1
");
            else
            {
                int t = Query(1,sb);
                printf ("%d
",t); //该死的cin cout 
            }     
      } 
   }
    
 return 0;
} 
/*

3 5 5
2
4
3
3
3
*/