题意:
x*y的板,贴单位高 wi长的便条,每次从可用的左上空位贴,
给出一个便条,问是否可贴下.坐标.
主要是用线段树如何用的问题...加深理解的题
#include <cstdio> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 222222; int h , w , n; int MAX[maxn<<2]; ///线段树中存什么?存最大值_什么的最大值?可用宽度最大值 //线段树的每一个整点上都可以存一个值..根据坐标的定义和存值的含义不同 //有不同的应用 ///下标是便条个数...no no no,是板高!也就是纵向建树 void PushUP(int rt) { MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]); } void build(int l,int r,int rt) { MAX[rt] = w; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } int query(int x,int l,int r,int rt) { if (l == r) { MAX[rt] -= x; return l; }//如果可用的第一个最大值在左边,就询问左儿子,否则才询问右儿子. //这样可以保证找到最上面的空位 int m = (l + r) >> 1; int ret = (MAX[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;//>n也没有用,和==n的情况一样,优化! build(1 , h , 1);//从1位置开始的 while (n --) { int x; scanf("%d",&x); if (MAX[1] < x) puts("-1");//MAX[1]表示整个区间上的最大值 else printf("%d\n",query(x , 1 , h , 1)); }//因为是可以就插入,不行就抛弃,所以query中可包含update } return 0; }