NC210383. 干草堆tower
描述
输入描述
第1行：一个单一的整数N。 第2~N+1行：一个单一的整数:W_i。
输出描述
第一行：一个单一的整数，表示Bessie可以建立的草包堆的最高高度。
示例1
输入:
3 1 2 3
输出:
2
C++(clang++11) 解法, 执行用时: 17ms, 内存消耗: 2680K, 提交时间: 2020-11-04 08:49:27
#include<bits/stdc++.h>
using namespace std;
const int nn=101103;
int n,tp,ans[nn],st[nn];
long long w[nn],f[nn];
bool cmp(int a,int b){return f[a]+w[a]<f[b]+w[b];}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",w+i);
for(int i=n,j;i;i--){
w[i]+=w[i+1];
j=st[upper_bound(st,st+tp+1,i,cmp)-st-1];
f[i]=w[i]-w[j],ans[i]=ans[j]+1;
while(f[i]+w[i]<=f[st[tp]]+w[st[tp]])tp--;
st[++tp]=i;
}return printf("%d\n",ans[1]),0;
}