洛谷 P2300 合并神犇

洛谷

听说这题可以\(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;

}

巴特西

洛谷 P2300 合并神犇

最新文章

热门文章