洛谷P1714切蛋糕

该题目就是求这n个数的前缀和所组成的数组的所有子区间的左端点和右端点相差不超过m，且他们的前缀和差最大，求出这个最大值即可。

而朴素算法肯定会T,而我们发现如果前缀和最大的话，则前缀和的值一定是满足单调递增的，因此可以用单调队列优化。

#include <iostream>//单调队列，队列里满足后加的数要比之前的大

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#define N 500011

using namespace std;

deque <int> qmax;

int n, m, ans;

int data[N], sum[N];

int main()

{

 	scanf("%d%d", &n, &m);

 	for (int i = 1; i <= n; i++)

 	 	scanf("%d", &data[i]), sum[i] = sum[i - 1] + data[i];

 	for (int i = 1; i <= n; i++)

 	{

	 	while (qmax.size() && sum[i] < sum[qmax.back()]) //队列中要满足单调递增，而为什么要选择出队，而不选择不加入该数呢，因为队列中的值已经更新了ans所以已经没用了，但是加入的数还有可能更新答案，因此需要加入该数

			qmax.pop_back();

	 	qmax.push_back(i);

	 	while (qmax.back() - qmax.front() > m) qmax.pop_front();

 	 	ans = max(ans, sum[qmax.back()] - sum[qmax.front()]);//sum[qmax.front()]一定是最小的

 	}

 	printf("%d", ans);

 	return 0;

}

巴特西

洛谷P1714切蛋糕

最新文章

热门文章