题解 P1969 【积木大赛】
阿尔萨斯
2019-04-20 11:02:27
这题普及-……
然而我并没有想到简单的方法,直到看了别的大佬打的贼短的代码才发现这题这么简单……
第一眼看到就觉得是多次找区间最小值,然后二分去找,然后想到线段树(我不会别的算法了)这里线段树不需要修改值,所以也不需要打lazytag,蛮好打的。
线段树是学[皎月半撒花](https://www.luogu.org/space/show?uid=28313)的,膜一下 不会线段树的[来这里学一下](https://www.luogu.org/problemnew/solution/P3372)
思路大概就是每次铺当前区间尽可能多,然后从要求的最低处二分
例:2 3 4 1 2
第四个“1”就是最低处,所以【1,5】铺(1-0),也就是1,然后考虑【1,3】和【5,5】
【1,3】中最低处是第一个“2”,所以铺(2-1),因为之前都铺过1层了。以此类推……
代码中有个地方卡了我很久……我太弱了 _qwq_
贴代码,看注释
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<ctime>
#define ll int
using namespace std;
inline ll read()//快速读入可有可无
{
char c=getchar();
ll s=0,t=1;
while(c<'0'||c>'9')
{
if(c=='-')t*=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=s*10+c-'0';
c=getchar();
}
return s*t;
}
ll ans[400004],a[100001],n,answer=0;//a是每个地方需要搭的高
inline ll ls(ll x)//开始线段树,这是返回左子树的节点值,会线段树的不用看了,线段树打发很多
{
return x<<1;
}
inline ll rs(ll x)//右子树
{
return x<<1|1;
}
void build(ll l,ll r,ll s)//递归建树
{
if(l==r)//如果触底就返回
{
ans[s]=l;
return;
}
ll mid=(l+r)>>1;
build(l,mid,ls(s));//二分建树
build(mid+1,r,rs(s));
ll s1,s2;
s1=a[ans[ls(s)]];//列出左右子树中最低处的高
s2=a[ans[rs(s)]];
if(s1<s2)ans[s]=ans[ls(s)];//返回最低处
else ans[s]=ans[rs(s)];
}
ll find(ll s,ll l,ll r,ll xl,ll xr)//注意返回值为位置 ,高度要用a[find(?????)]表示
{
if(xl<=l&&r<=xr)return ans[s];//如果这个节点应该查询,也就是被查询的左右区间包含,就返回
ll mid=(l+r)>>1,lo,lo2,k;
if(xl<=mid)//没错就是这里!一定要注意如果该节点左子树不用查询就直接返回右子树的值,否则再比较
{
lo=find(ls(s),l,mid,xl,xr);//lo就是左子树中最低点的位置
k=lo;//用于比较,记录最低点
if(mid<xr)
{
lo2=find(rs(s),mid+1,r,xl,xr);//lo2是右子树最低点位置
if(a[lo2]<a[lo])k=lo2;//比较
}
}
else//如果没有左子树就直接查询右子树
{
lo=find(rs(s),mid+1,r,xl,xr);
k=lo;
}
return k;
}
void f(ll l,ll r,ll h)//h是之前的高度
{
if(l>r)return;//奇怪的判断,分别判断这个区间是否存在,是否越界*2
if(r<1)return;
if(l>n)return;
ll lo=find(1,1,n,l,r),height;
height=a[lo];
answer+=height-h;//answer加上(当前高度-之前的高度)
f(l,lo-1,height);//二分
f(lo+1,r,height);
}
int main()
{
n=read();
for(ll i=1;i<=n;i++)a[i]=read();
build(1,n,1);
f(1,n,0);
cout<<answer;
}
```
考场上好好想想简单的方法吧,打线段树超耗时