P1714 切蛋糕（单调队列，最大不定长子段和问题，multiset，前缀和）

· · 题解

P1714 切蛋糕

没有用multiset维护子段的吗？我来写一波！

简要题意

求给定数组中最大的长度不超过给定长度的子段和.

题目分析

前缀和的使用

看到有个“前缀和”的tag，就明白要用前缀和表示

我们发现，如果直接用数组本身计算这个最大不定子段和，我们需要三重循环（n,m加上一重计算各元素的和）

为了减小维度，提高效率，我们可以预处理前缀和以通过O(1)得到各元素的和.

multiset的使用

如果直接用暴力计算最大不定子段和，我们需要枚举n,m，复杂度为O(nm)，注意数据范围为50w，显然超时.

反向分析时间复杂度，我们发现大约O(n\:log\:n)级别的算法可以accept，所以思考如何优化枚举.

可以发现，求最大不定子段和，实际上就是在求区间前缀和的差的最大值，也就是说，我们要维护在m大小区间内，前缀和的最小值.

也就是说，我们需要一个数据结构，它可以：

按队列的先后进入顺序实现元素的插入和删除， 而且还可以很方便地获得此时其中的最小值（即本身能够排序）.

然后我开始想怎么用priority_queue实现第一点。。。

忽然想起来multiset（可重集）可以满足以上的要求，multiset内部实现是红黑树，本身有序，而且插入和删除操作都是log级别的，满足对复杂度的分析.

想要了解更多关于multiset的知识，请点击这里.

然后本题就解决了.

程序实现

#include<bits/stdc++.h>
#define ll long long
#define maxn 500010
using namespace std;
ll n,m,lucky[maxn];
ll sum[maxn],ans=-0x3f3f3f3f;
multiset<ll >st;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&lucky[i]);
        sum[i]=sum[i-1]+lucky[i];//求前缀和
    }
    multiset<ll >::iterator it;
    st.insert(sum[0]);
    for(int i=1;i<=n;i++){
        if(i<=m){//注意边界，i==m时恰好前面的元素都可以取完
            ll a=*st.begin();
            ans=max(ans,sum[i]-a);//取较大值
        }
        else{
            it=st.find(sum[i-m-1]);//find返回的是一个迭代器
            st.erase(it);//erase删除的也是迭代器所指的元素
            ll a=*st.begin();//取最小值
            ans=max(ans,sum[i]-a);
        }
        st.insert(sum[i]);//最后再入multiset，因为我们不考虑区间大小为0的情况
    } 
    printf("%lld\n",ans);
    return 0;
}

题后总结

可以反向分析时间复杂度以明白应该使用什么算法.

这不是正解！正解（单调队列）可以达到O(n)的复杂度！