传送门：HDU2795
题意：h*w的木板,放进一些1*L的物品,每次优先放到能容纳且最上边最左边的位子，求每个物品在第几行。 思路：用线段树维护每一行的剩余长度，每次更新时优先询问左子树。代码中我将update和query合到一起了。
代码：
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #define ll long long #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int,int>P; const int MAXN=200010; int h,w,n; int num[MAXN<<2]; void pushup(int rt) { num[rt]=max(num[rt<<1],num[rt<<1|1]); } void build(int l,int r,int rt) { if(l==r) { num[rt]=w; return ; } int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } int query(int x,int l,int r,int rt) { if(l==r) { num[rt]-=x; return l; } int mid=(l+r)>>1; int ans; if(num[rt<<1]>=x) ans=query(x,lson); else ans=query(x,rson); pushup(rt); return ans; } int main() { int t; while(~scanf("%d%d%d",&h,&w,&n)) { if(h>n)h=n; build(1,h,1); while(n--) { scanf("%d",&t); printf("%d\n",num[1]>=t?query(t,1,h,1):-1); } } return 0; }
