题解 P1969 【积木大赛】

2019-04-20 11:02:27


这题普及-…… 然而我并没有想到简单的方法,直到看了别的大佬打的贼短的代码才发现这题这么简单……

第一眼看到就觉得是多次找区间最小值,然后二分去找,然后想到线段树(我不会别的算法了)这里线段树不需要修改值,所以也不需要打lazytag,蛮好打的。 线段树是学皎月半撒花的,膜一下 不会线段树的来这里学一下

思路大概就是每次铺当前区间尽可能多,然后从要求的最低处二分

例:2 3 4 1 2

第四个“1”就是最低处,所以【1,5】铺(1-0),也就是1,然后考虑【1,3】和【5,5】

【1,3】中最低处是第一个“2”,所以铺(2-1),因为之前都铺过1层了。以此类推……

代码中有个地方卡了我很久……我太弱了 qwq

贴代码,看注释

#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;
} 

考场上好好想想简单的方法吧,打线段树超耗时