题解 P1969 【积木大赛】

阿尔萨斯

2019-04-20 11:02:27

Solution

这题普及-…… 然而我并没有想到简单的方法,直到看了别的大佬打的贼短的代码才发现这题这么简单…… 第一眼看到就觉得是多次找区间最小值,然后二分去找,然后想到线段树(我不会别的算法了)这里线段树不需要修改值,所以也不需要打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; } ``` 考场上好好想想简单的方法吧,打线段树超耗时