|
|
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795
  /**//*
 题意：
对于w*h(w <= 10^9, h <= 10^9 )的一块区域，连续摆放1*wi的木板，木板不能
旋转，如果能放下就选择最靠上的位置摆放，并且输出行号，如果找不到直接输出-1。
解法：
线段树
思路：
将h这一维映射到线段树的区间，w这一维则对应区间点上的最大值，每次询问时
做一次插入操作，如果当前访问的结点的最大值小于给定值，直接返回-1。否则，左
子树的最大值大于当前值，那么访问左子树，小于则访问右子树，直到叶子结点。如
果成功找到，说明给定值小于叶子结点的值，将叶子结点的值减去给定值，然后递归
更新内部结点的最值。
 */
#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;
}
|