本文共 1424 字，大约阅读时间需要 4 分钟。
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2795
题目描述： 一个h * w的木板， 要将n个1 * L[i]的木条放进去， 要求的优先最上面， 优先最左面， 输出放入每一个木条应放入的行号
解题思路： 查询区间最大值， 并且尽可能的向靠上的（小号开头的）区间中放置， 其实我们并不关心到底是否向左放， 我们只需要保证一旦有空就靠边放就行， 所以用一个减法就完全可以表示了， 我们只需要用tree[i] 表示第i行还剩余的容量， 放置时更新最大值就可以了
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1using namespace std;int h, w, n;const int treen = 222222;int tree[treen<<2];void Pushup(int rt) { tree[rt] = max( tree[rt<<1], tree[rt<<1|1] );}void build( int l, int r, int rt ) { tree[rt] = w; if( l == r ) return; int m = (l + r) >> 1; build( lson ); build( rson ); return;}int query( int x, int l, int r, int rt ) { if( l == r ) { tree[rt] -= x; return l; } int m = (l + r) >> 1; int ret = (tree[rt<<1] >= x) ? query(x , lson) : query(x , rson); Pushup(rt); return ret;}int main() { while( ~scanf( "%d%d%d", &h, &w, &n ) ) { if( h > n ) h = n; build(1, h, 1); while( n-- ) { int L; scanf( "%d", &L ); if( tree[1] < L ) printf( "-1\n" ); else { int ret = query(L, 1, h, 1); printf( "%d\n", ret ); } } } return 0;}
思考： 自己码这个代码的时候特别不专心， 然后现在我接触到的线段树一个是求 最大值， 一个是求和， 然而以后肯定各种恶心的树层出不穷， 先把线段树学好， 然后进程溢出首先检查自己的输入......
转载于:https://www.cnblogs.com/FriskyPuppy/p/7294559.html
