HDU 2795 Billboard(区间求最大值的位置update的操作在query里做了)

Billboard

通过这题,我知道了要活用线段树的思想,而不是拘泥于形式, 就比如这题 显然更新和查询放在一起很简单 但如果分开写 那么我觉得难度会大大增加

【题目链接】Billboard

【题目类型】区间求最大值的位置update的操作在query里做了

&题意:

h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子

&题解:

思路:每次找到最大值的位子,然后减去L

线段树功能:query

区间求最大值的位置(直接把update的操作在query里做了)

【时间复杂度】\(O(nlogn)\)

&代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 9 ;
int h,w,n;
int seg[maxn<<2];
inline void PushUp(int rt)
{
seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);
}
void Build(int b,int e,int rt)
{
if (b==e){
seg[rt]=w;
return;
}
int m=b+e>>1;
Build(b,m,rt<<1);
Build(m+1,e,rt<<1|1);
PushUp(rt);
}
//把更新和查询放在了一起
int Query(int xx,int b,int e,int rt)
{
if (b==e){
seg[rt]-=xx;
return b;
}
int m=b+e>>1;
int re=0;
//这里保证了先从小的序号开始找
if (seg[rt<<1]>=xx)
re=Query(xx,b,m,rt<<1);
else
re=Query(xx,m+1,e,rt<<1|1);
PushUp(rt);
return re;
}
void Solve()
{
while(~scanf("%d%d%d",&h,&w,&n)){
h=min(h,n);
Build(1,h,1);
for(int i=0;i<n;i++){
int t;
scanf("%d",&t);
if (seg[1]<t) puts("-1");
else {
printf("%d\n",Query(t,1,h,1));
}
}
}
}
int main()
{
Solve();
return 0;
}
上一篇:C++基础:二维数组动态的申请内存和释放内存


下一篇:手机浏览器不支持 IDBObjectStore.getAll