chail's Blog
博客 分类 标签
chail's Blog

目录

目录

洛谷 P1714 切蛋糕[单调队列，前缀和]

 收录于  类别 算法足迹
     约 1400 字   预计阅读 7 分钟 

洛谷 P1714 切蛋糕[单调队列，前缀和]

大家新年好呀！虽然新年已经过去了…各位今年过得还开心吗？反正我是好好休息了几天，再次回来做题感觉脑子已经生锈了，所以来做一些不那么难的题复健。

来看看我们今天的题目吧！是一道需要注意一点细节的单调队列题！

今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 n 个相同的小块，每小块都有对应的幸运值。

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 m(m≤n) 小块的蛋糕。

请你帮他从这 n 小块中找出连续的 k(1≤k≤m) 块蛋糕，使得其上的总幸运值最大。

形式化地，在数列 ${p_n}中，找出一个子段中，找出一个子段[l,r](r-l+1\le m)，最大化，最大化\sum\limits_{i=l}^rp_i$。

第一行两个整数 n,m。分别代表共有 n 小块蛋糕，小 Z 最多只能吃 m 小块。

第二行 n 个整数，第 i 个整数 pi 代表第 i 小块蛋糕的幸运值。

仅一行一个整数，即小 Z 能够得到的最大幸运值。

5 2
1 2 3 4 5
9
6 3
1 -2 3 -4 5 -6
5
  • 对于 $20%$ 的数据，有 $1\le n\le100$。
  • 对于 $100%$ 的数据，有 $1\le n\le5\times 10^5$，$|p_i|≤500$。

保证答案的绝对值在 $[0,2^{31}-1]$ 之内。

第一眼看到此题：诶？这不最大子段和吗？直接利用二分查找前缀和最小值不就行了。诶等会？是 $m$ 的长度啊，那直接一个双指针更新最大值不就完了。诶等会，是长度在 $m$ 以内啊！那好吧，我用单调队列找 $m$ 长度内的最小前缀和总行了吧。

是的，这道题我前两次都没把这个条件看准。这道题的准确解法是用单调队列维护 $m$ 内的前缀和最小值并更新答案。

单调队列名言之：如果一个人比你小还比你强，那么你该走人了。（orz）

单调队列就是这样的一个队列，它是一个特殊的双端队列，队列内的元素满足某种单调性，比如大小单调递增，方便我们得到某种最值。每次新元素入队时，进行以下操作（以单调递增为例）：

1. 如果新元素比队尾元素小，把队尾那些不大于新元素的元素全踢出去，它们已经老了却没有新元素小，所以在接下来一定不会成为最小的元素。 2. 将队头那些已经超出窗口的元素踢出，它们已经太老了。

像这样，我们就可以维护好一个单调队列了，这里给出一个手写的代码：

class q{
	int qu[1000005];
	int l=1;
	int r=0;
public:
	bool emp(){
		return r<l;
	}
	void pb(int x){
		r++;
		qu[r]=x;
	}
	int f(){
		return qu[l];
	}
	int b(){
		return qu[r];
	}
	void popb(){
		r--;
	}
	void popf(){
		l++;
	}
	int len(){
		return r-l+1;
	}
};

这样的话，本题只要构建一个前缀和数组 $a$，维护好单调队列，每次将当前的前缀和减去队列中的前缀和的最小值就可以得到能得到的最大值了。

但是需要注意的是，本题的更新时机至关重要。因为我们总是维护最小值，那如果给的元素是单调递减的，队列中就永远只有当前元素了，这样就会导致一个元素也不选，结果为零。怎么办呢？我们先将 $0$ 入队，代表 $a[0]$，也就是一个还没选的情况。接着先去将队列中过期的元素弹出，再更新答案，最后踢出队尾那些老而大的元素。这样就可以得到正确的答案了。

#include <iostream>
#include <algorithm>
using namespace std;
int a[500005] = {0};
class q{
	int qu[1000005];
	int l=1;
	int r=0;
public:
	bool emp(){
		return r<l;
	}
	void pb(int x){
		r++;
		qu[r]=x;
	}
	int f(){
		return qu[l];
	}
	int b(){
		return qu[r];
	}
	void popb(){
		r--;
	}
	void popf(){
		l++;
	}
	int len(){
		return r-l+1;
	}
};
q miq;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >>n >>m;
	for(int i=1;i<=n;++i){
		int pi;
		cin >> pi;
		a[i] = a[i-1]+pi;
	}
	int res = -1e9;
	miq.pb(0);
	for(int i=1;i<=n;++i){
		while(!miq.emp() && miq.f()+m<i) miq.popf();
		if(miq.f()!=i){
			res = max(res, a[i]-a[miq.f()]);
		}
		while(!miq.emp() && a[miq.b()]>=a[i]) miq.popb();
		miq.pb(i);
	}
	cout <<res;
	return 0;
}

单调队列告诉我们，要不断地提升自己，要做一个有实力的老资历。

更新于 2026-02-22
 | 主页