当前位置：首页 > news >正文

洛谷P1714 切蛋糕（单调队列经典问题）

news 来源：原创 2024/5/3 15:32:33

传送门

一开始很容易想到尺取，但是好像又不太一样，尺取解决的一般是区间和接近某个数或者区间内讨论数的种类个数，而本题实际上是解决最大不定长连续子段和

然后不难想到最大连续和的经典问题，然后不难想到前缀和的 $O(n^2)$ 算法，显然会 $T L E$ ，那么参考最大连续和的前缀和优化：

假设以第 $j$ 个数为终点的最大子序列和的起点是 $i$ ，于是结果为 $s u m [j] - s u m [i - 1]$ 。因为我们要维护最大前缀和， $s u m [i - 1]$ 必然是 $s u m [1], s u m [2], . . ., s u m [j - 1]$ 中的最小值。这样，如果在维护计算 $s u m$ 数组的时候，同时维护之前的最小值，那么就可以求出最大连续和。时间复杂度 $O (n)$

但是本题并不是保存每个位置前缀和的最小值，因为限定区间长度为 $m$ ，那么仔细想想也就是每个位置前面长度为 $m$ 前缀和的最小值，这不就是经典的单调队列问题——滑动窗口的最小值吗，那么使用前缀和+单调队列即可

ps:因为区间[l,r]的和为前缀和sum( r )-sum(l-1)，因此实际上取的m为m+1，需要注意

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=5e5+10;

int a[maxn],q[maxn];

int main(){
    //freopen("cake.in","r",stdin);
    //freopen("cake.out","w",stdout);
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    m++;
    int l=0,r=0,ans=-inf;
    for(int i=1;i<=n;i++){
        while(l<r && i-q[l]+1>m) l++;
        while(l<r && a[i]<a[q[r-1]]) r--;
        q[r++]=i;
        ans=max(ans,a[i]-a[q[l]]);
        //cout<<ans<<endl;
    }
    cout<<ans<<"\n";
    return 0;
}