洛谷题单指南-常见优化技巧-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;
}