洛谷题单指南-常见优化技巧-P1714 切蛋糕

原题链接：https://www.luogu.com.cn/problem/P1714

题意解读：求长度不超过m的最大子段和

解题思路：

1、暴力法

设a[N]表示原数组，s[N]是a[N]的前缀和，对于每一个元素s[i]，计算其与前m个元素之差，取差值最大值，用代码表示：

for(int i = 1; i <= n; i++)
{
    for(int j = i - 1; j >= i - m && j >= 0; j--)
    {
        ans = max(ans, s[i] - s[j]);
    }
}

76分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
int n, m;
int a[N], s[N];
int ans = INT_MIN;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    for(int i = 1; i <= n; i++)
    {
        for(int j = i - 1; j >= i - m && j >= 0; j--)
        {
            ans = max(ans, s[i] - s[j]);
        }
    }

    cout << ans;
    return 0;
}

2、单调队列优化

仔细观察一下暴力法的代码：

此段代码可以改写成：

for(int i = 1; i <= n; i++)
{
    int minx = INT_MAX;
    for(int j = i - 1; j >= i - m && j >= 0; j--)
    {
       minx = min(minx, s[j]);
    }
    ans = max(ans, s[i] - minx);
}

进一步观察代码：

红色框部分是要在长度为m的窗口内找最小值，因此可以采用单调队列来优化

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
int n, m;
int a[N], s[N];
int ans = INT_MIN;
int q[N], head = 0, tail = -1;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    for(int i = 0; i <= n; i++) //需要注意的是，i需要从0开始，这样队列第一个元素可能是0,是为了保证区间和正确：s[r]-s[l-1]
    {
        while(head <= tail && i - q[head] > m) head++;
        while(head <= tail && s[i] <= s[q[tail]]) tail--;
        ans = max(ans, s[i] - s[q[head]]);
        q[++tail] = i;
    }

    cout << ans;
    return 0;
}