自动搬运

查看原文

来自洛谷，原作者为

	fyfy **

搬运于2025-08-24 21:36:06，当前版本为作者最后更新于2018-09-07 09:38:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

听说这题可以$n^2$水过去，

不过这里介绍一种O(n)的做法。

$f[i]$为第$[1,i]$位合并的次数

$pre[i]$为第$[1,i]$位最末尾的数

$j$为满足$sum[i]-sum[j]>=pre[j]$的最大数

$f[i]=f[j]+i-j-1$

$pre[i]=sum[i]-sum[j]$

显然$pre[i]$越小越好，这样找到一个就可以退出。

所以可以直接用单调队列优化。

时间复杂度$O(n)$。

代码，注意开$\texttt{long~long}$：

#include <bits/stdc++.h>
using namespace std;
typedef int _int;
#define int long long

const int N=200010;
int head,tail=1;
int n,f[N],pre[N],sum[N],q[N];

_int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int x;
    for (int i=1;i<=n;++i)
        cin>>x,sum[i]=sum[i-1]+x;
    for (int i=1;i<=n;++i) {
        while (head+1<tail&&sum[i]>=sum[q[head+1]]+pre[q[head+1]])
            ++head;
        f[i]=f[q[head]]+1;
        pre[i]=sum[i]-sum[q[head]];
        while (head<tail&&sum[q[tail-1]]+pre[q[tail-1]]>sum[i]+pre[i])
            --tail;
        q[tail++]=i;
    }
    cout<<n-f[n];
    return 0;
}