|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2795
  /**//*
 題意：
對(duì)于w*h(w <= 10^9, h <= 10^9 )的一塊區(qū)域，連續(xù)擺放1*wi的木板，木板不能
旋轉(zhuǎn)，如果能放下就選擇最靠上的位置擺放，并且輸出行號(hào)，如果找不到直接輸出-1。
解法：
線段樹
思路：
將h這一維映射到線段樹的區(qū)間，w這一維則對(duì)應(yīng)區(qū)間點(diǎn)上的最大值，每次詢問時(shí)
做一次插入操作，如果當(dāng)前訪問的結(jié)點(diǎn)的最大值小于給定值，直接返回-1。否則，左
子樹的最大值大于當(dāng)前值，那么訪問左子樹，小于則訪問右子樹，直到葉子結(jié)點(diǎn)。如
果成功找到，說明給定值小于葉子結(jié)點(diǎn)的值，將葉子結(jié)點(diǎn)的值減去給定值，然后遞歸
更新內(nèi)部結(jié)點(diǎn)的最值。
 */
#include <iostream>
using namespace std;
#define maxn 200010
struct Tree  {
int Max;
int root, l, r;
}T[maxn*4];
int h, w, n;
void Build(int p, int l, int r) {
T[p].root = p;
T[p].l = l;
T[p].r = r;
T[p].Max = w;
  if(l == r) {
return ;
 }
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
}
int MMax(int a, int b) {
return a > b ? a : b;
}
int Insert(int p, int val) {
if(T[p].l == T[p].r) {
if(T[p].Max < val)
return -1;
T[p].Max -= val;
return T[p].l;
}
if(val <= T[p].Max) {
int x = 0;
if(val <= T[p<<1].Max) {
x = Insert(p<<1, val);
}else {
x = Insert(p<<1|1, val);
}
T[p].Max = MMax(T[p<<1].Max, T[p<<1|1].Max);
return x;
}else
return -1;
}
int main() {
int i, X;
while(scanf("%d %d %d", &h, &w, &n) != EOF) {
if(h > n)
h = n;
Build(1, 1, h);
for(i = 0; i < n; i++) {
scanf("%d", &X);
printf( "%d\n", Insert(1, X) );
}
}
return 0;
}
|