題目大意: 廣告牆高從上到下為h，寬左到右為w，還有n張廣告牌
用單位高度，寬度為wi的廣告牌去覆蓋牆
輸出廣告牌放的高度 (優先選擇最上面的，同一高度則放在最左邊)，不放不下則輸出 -1
解題思路: 建立線段樹，區間表示每個高度的剩余的寬度
最下層的結點(Tree[t].left==Tree[t].right)，存儲這一層剩余的寬度MAX
其他結點存儲左右子樹的剩余寬度MAX
查詢的時候，當此結點的MAX大於廣告牌的寬度則往下查找
當左右子樹都同時滿足的情況下，優先選擇左子樹，若發現MAX不滿足則停止搜索這棵子樹
代碼:
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max 210000
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b?a:b
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1+1)
typedef struct{
int left,right;
int leftmax,rightmax,max;
}Node;
Node Tree[Max<<2];
int n,h,w,pd,kk;
void Build(int t,int l,int r) //以1為根節點建立[l,r]的線段樹
{
int mid;
Tree[t].left=l,Tree[t].right=r;
if(Tree[t].left==Tree[t].right)
{
Tree[t].max=Tree[t].leftmax=Tree[t].rightmax=w;
return ;
}
mid=MID(Tree[t].left,Tree[t].right);
Build(L(t),l,mid);
Build(R(t),mid+1,r);
Tree[t].leftmax=Tree[L(t)].max;
Tree[t].rightmax=Tree[R(t)].max;
Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);
}
void Query(int t,int l,int r,int m)
{
int mid;
if(Tree[t].left==l&&Tree[t].right==r&&l==r) //一直找到那個點l==r
{
if(Tree[t].max>=m)
{
Tree[t].max-=m; //找到那點，標記
kk=Tree[t].left;
pd=1;
}
return ;
}
mid=MID(Tree[t].left,Tree[t].right);
if(Tree[t].max<m) //若MAX小於m則退出，不搜索子樹
return ;
if(Tree[t].leftmax>=m) //優先選擇滿足情況的左子樹
Query(L(t),l,mid,m);
else if(Tree[t].rightmax>=m) //左子樹不滿足，才選擇右子樹
Query(R(t),mid+1,r,m);
else
return ;
Tree[t].leftmax=Tree[L(t)].max;
Tree[t].rightmax=Tree[R(t)].max;
Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);
}
int main()
{
int i,m;
while(scanf("%d%d%d",&h,&w,&n)!=EOF)
{
if(h>n)
h=n;
memset(Tree,0,sizeof(Tree)); //初始化線段樹
Build(1,1,h); //建樹
for(i=0;i<n;i++)
{
scanf("%d",&m);
pd=0;
Query(1,1,h,m); //查詢[1,h]滿足MAX>=n的區間
if(pd)
printf("%d\n",kk);
else
printf("-1\n");
}
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max 210000
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b?a:b
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1+1)
typedef struct{
int left,right;
int leftmax,rightmax,max;
}Node;
Node Tree[Max<<2];
int n,h,w,pd,kk;
void Build(int t,int l,int r) //以1為根節點建立[l,r]的線段樹
{
int mid;
Tree[t].left=l,Tree[t].right=r;
if(Tree[t].left==Tree[t].right)
{
Tree[t].max=Tree[t].leftmax=Tree[t].rightmax=w;
return ;
}
mid=MID(Tree[t].left,Tree[t].right);
Build(L(t),l,mid);
Build(R(t),mid+1,r);
Tree[t].leftmax=Tree[L(t)].max;
Tree[t].rightmax=Tree[R(t)].max;
Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);
}
void Query(int t,int l,int r,int m)
{
int mid;
if(Tree[t].left==l&&Tree[t].right==r&&l==r) //一直找到那個點l==r
{
if(Tree[t].max>=m)
{
Tree[t].max-=m; //找到那點，標記
kk=Tree[t].left;
pd=1;
}
return ;
}
mid=MID(Tree[t].left,Tree[t].right);
if(Tree[t].max<m) //若MAX小於m則退出，不搜索子樹
return ;
if(Tree[t].leftmax>=m) //優先選擇滿足情況的左子樹
Query(L(t),l,mid,m);
else if(Tree[t].rightmax>=m) //左子樹不滿足，才選擇右子樹
Query(R(t),mid+1,r,m);
else
return ;
Tree[t].leftmax=Tree[L(t)].max;
Tree[t].rightmax=Tree[R(t)].max;
Tree[t].max=MAX(Tree[t].leftmax,Tree[t].rightmax);
}
int main()
{
int i,m;
while(scanf("%d%d%d",&h,&w,&n)!=EOF)
{
if(h>n)
h=n;
memset(Tree,0,sizeof(Tree)); //初始化線段樹
Build(1,1,h); //建樹
for(i=0;i<n;i++)
{
scanf("%d",&m);
pd=0;
Query(1,1,h,m); //查詢[1,h]滿足MAX>=n的區間
if(pd)
printf("%d\n",kk);
else
printf("-1\n");
}
}
return 0;
}
