HDU 2795 Billboard (线段树+贪心)

手动博客搬家:本文发表于20170822 21:30:17, 原地址https://blog.csdn.net/suncongbo/article/details/77488127

URL: http://acm.hdu.edu.cn/showproblem.php?pid=2795题目大意:有一个hw的木板 (h, w<=1e9), 现在有n (n<=2e5)张1xi的海报要贴在木板上,按1~n的顺序每次贴海报时会选择最上的一排的最左边贴 (海报不能互相覆盖), 求每张海报会被贴在哪一行。最上方的一行编号为1, 以此类推。

样例解析:

如下

column 12345
row 1: 11333
row 2: 2222X
row 3: 444XXX: 未摆放;

对应行列上的数是摆放在此的海报的编号思路分析:本题实际上是一个贪心的思想。

每次可以从最上一行向下枚举剩余的空间,找到第一个能够贴上第i个海报的行,然后输出,更新即可。

时间复杂度O(n^2), 无法AC.

于是我们可以考虑二分的思想:

用线段树维护每一行剩余的空间的大小的最大值。

每次查询时,采用类似于二分答案的方法,每到达线段树的一个节点,若它的左子树最大值>=xi, 则左子树中必存在合法的最大答案,查询左子树;

假如左子树中的行无法装下第i张海报,但右子树最大值<=xi, 此时说明右子树中存在合法的最大答案,于是“退而求其次”,查询右子树。

如果两棵子树最大值都>xi, 则无法张贴此海报,于是输出-1.

查询完毕后,做一个单点修改,将答案所在的行剩余空间减去xi.

其实,最后一种情况不需要考虑。

假如整个[1, h]区间的最大值<xi, 则直接输出-1, 无需查询。

但是我们无法开4e9 (4h)如此大的数组,怎么办呢?

其实假如h>n, 那么下面的(h-n)行全部浪费了,不影响结果。

因此,h=min(h,n);

只开8e5 (4
n)的数组即可。

代码呈现:(Time: 3151 MS; 11256 KB; Code: 1576 B)

#include<cstdio>
#include<algorithm>
using namespace std; const int MAXN = 2e5;
struct Node
{
int left,right;
int maxi;
};
struct SegmentTree
{
Node nd[MAXN*4+8]; void init()
{
for(int i=1; i<=MAXN*4; i++)
{
nd[i].left = nd[i].right = nd[i].maxi = 0;
}
} void build(int lbound,int rbound,int pos,int tot)
{
nd[pos].left = lbound;
nd[pos].right = rbound;
if(lbound==rbound)
{
nd[pos].maxi = tot;
return;
}
int mid = (lbound+rbound)/2;
build(lbound,mid,2*pos,tot);
build(mid+1,rbound,2*pos+1,tot);
nd[pos].maxi = tot;
} void modify_subs(int bound,int val,int pos)
{
int mid = (nd[pos].left+nd[pos].right)/2;
if(nd[pos].left==nd[pos].right)
{
nd[pos].maxi-=val;
return;
}
if(bound<=mid) modify_subs(bound,val,2*pos);
else modify_subs(bound,val,2*pos+1);
nd[pos].maxi = max(nd[2*pos].maxi,nd[2*pos+1].maxi);
} int query(int pos,int val)
{
int mid = (nd[pos].left+nd[pos].right)/2;
if(nd[pos].left==nd[pos].right) return nd[pos].left;
int ans;
if(val<=nd[2*pos].maxi) return query(2*pos,val);
else return query(2*pos+1,val);
}
};
SegmentTree sgt;
int n,m,p; int main()
{
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
{
if(n>p) n = p;
sgt.init();
sgt.build(1,n,1,m);
for(int i=1; i<=p; i++)
{
int x;
scanf("%d",&x);
if(sgt.nd[1].maxi < x)
{
printf("-1\n");
continue;
}
int ans = sgt.query(1,x);
printf("%d\n",ans);
if(ans>0) sgt.modify_subs(ans,x,1);
}
} return 0;
}
上一篇:HDU 2795 Billboard 线段树,区间最大值,单点更新


下一篇:Flask-DebugToolbar