题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的物体,每次存放物体都是优先放在最高的位置,其次优先放在最靠右的位置,对于每一次放入物品,输出这个物品放在第几行。
思路:用线段树,每个线段初始val为w,每次查询返回最高一行可以存放的位置,并且更新区间节点最大值val
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long LL; const int nMax = 200020; struct{ int l,r,val; }node[nMax*3]; int h,w; void build(int l, int r, int u){ node[u].val = w; node[u].l=l; node[u].r=r; if(l == r){ return; } int m = (l+r)/2; build(l , m ,u*2); build(m+1 , r, u*2 + 1); } int update(int p,int u){ int l = node[u].l; int r = node[u].r; if(l == r){ if(node[u].val>=p){ node[u].val -= p; return r; }else{ return -1; } } int ans = -1; if(p<=node[2*u].val)ans = update(p,2*u); else if(p<=node[2*u+1].val)ans = update(p,2*u+1); node[u].val = max(node[2*u].val,node[2*u+1].val); return ans; } int main(){ int n , a ; while(scanf("%d%d%d",&h,&w,&n)!=EOF){ build(1,min(h,n),1); while(n--){ scanf("%d",&a); int loc = update(a , 1); // cout<<loc<<endl; printf("%d\n",loc); } } return 0; }
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码
HDOJ使用指南——公开版.docHDOJ使用指南——公开版.docHDOJ使用指南——公开版.doc