Solve this Problem with the Priority Queue

单调队列的主要目标其实跟单调栈的主要目标比较相似，都是在一个单调问题中，直接排除一些可以排除的答案进行运算。

在本题中，我们会采用单调队列来解决。首先，我们采用前缀和来进行快速计算。然后，在前缀的前提下，我们会在本题中使用一个策略，那就是：如果有两个位置的前缀和\(sum[i]>sum[j],其中i<j\)，那么处于\(i\)位置的元素对于我们来讲，是毫无用处的。原因是，如果我们要在\(m\)长度内获得和最大的子序列，对于一个这样前缀和又大、又靠前的元素，最优解绝不是由这个元素组成的。

我们来用几个代码块来简述我们的策略。

// ll stands for long long
const int maxn = 300200;
ll n, arr[maxn], sum[maxn], m, q[maxn];

声明了几个变量，not a big deal.

ll l = 1, r = 1, ans = -1e9;
q[1] = 0;
for (int i = 1; i <= n; i++)
{
    while (l <= r && q[l] < i - m)
        l++;
    ans = max(ans, sum[i] - sum[q[l]]);
    while (l <= r && sum[q[r]] >= sum[i])
        r--;
    q[++r] = i;
}

我们首先定义队头、队尾，还有一个无穷小的答案。之后，我们来枚举元素\(i\)。我们在循环中首先淘汰掉那些距离超过\(m\)的元素。之后我们来记录答案。然后就到我们实施策略的时候了。我们淘汰掉那些不属于最优解的答案。之后，我们记录在位置\(++r\)的答案为\(i\)。

完整代码：

	// CH1201.cpp
	#include <iostream>
	#include <algorithm>
	#include <cstdio>
	#define ll long long
	using namespace std;
	const int maxn = 300200;
	ll n, arr[maxn], sum[maxn], m, q[maxn];
	int main()
	{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	scanf("%lld", &arr[i]), sum[i] = sum[i - 1] + arr[i];
	ll l = 1, r = 1, ans = -1e9;
	q[1] = 0;
	for (int i = 1; i <= n; i++)
	{
	while (l <= r && q[l] < i - m)
	l++;
	ans = max(ans, sum[i] - sum[q[l]]);
	while (l <= r && sum[q[r]] >= sum[i])
	r--;
	q[++r] = i;
	}
	printf("%lld", ans);
	return 0;
	}

view raw CH1201.cpp hosted with by GitHub