从中选取一个高度最高的塔$A$,记塔高为$h_A$,再记录再选取一个基底最窄的塔$B$,记塔高为$h_B$。

并将每一层的结尾堆从下往上编号分别记录下来,标为$A_i,B_i$。

那么有$h_A\ge h_B$,$A_1\ge B_1$,还有一个稍微需要拐一下弯,就是$A_{h_A}\le B_{h_B}$,怎么理解?反过来,理解一下,如果$A_{h_A}> B_{h_B}$,那么$\forall A_i> B_i$,等价于$A$的每一层宽度都不比$B$小,而$A$反而还高于$B$,很明显就是不现实的。

因此我们可以得出一个结论,$ \exists k,A_{k-1}\ge B_{k-1},A_k\le B_{k-1}$,也就是说方案$A$第$k$层的草堆完全被方案$B$第$k$层的草堆包含。

在$k$层之前,可以使用$B$塔的,在$k$层之后,可以使用$A$塔的,剩下的塞到$k$层上。

这样得出的新塔,底层宽度小于$A$,高度与$A$一样。

因此,存在一个方案,满足高度最高,且最底层宽度最小。

因此求解底层宽度最小,也就相当于求解高度最高。

之后倒序处理,设$f_i$为用$[i,n]$的最底层的最窄宽度,$g_i$为高度,搞一搞前缀和$s_i$,那么有:

$\large f_i=\min\limits_{i<j\le n,f_j\le s_{j-1}-s_{i-1}}\{s_{j-1}-s_{i-1}\}$

因为$-s_i$是线性递增的,用单调队列维护一下就好了。

队列里面的数应该关于$f_i-s_{i-1}$单调递增的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=1e5+5;
inline void qr(int &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
int sum[N],q[N],f[N],g[N];
int main()
{
    int n;qr(n);
    for(int i=1,x;i<=n;i++)qr(x),sum[i]=sum[i-1]+x;
    int l=1,r=1;q[1]=n+1;
    for(int i=n;i;i--)
    {
        while(l<r&&sum[q[l+1]-1]-sum[i-1]>=f[q[l+1]])++l;//找到最极限的j,压缩这一行的宽度
        f[i]=sum[q[l]-1]-sum[i-1];
        g[i]=g[q[l]]+1;
        while(l<r&&f[i]-sum[i-1]<f[q[r]]-sum[q[r]-1])--r;
        q[++r]=i;
    }
    printf("%d",g[1]);
    return 0;
}