|
题目链接: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; }
|