洛谷 P2629 好消息，坏消息（单调队列）

题目链接

首先想到的就是暴力前缀和，枚举一个区间每次统计前缀和，前缀和的某一个值为负数时就退出

如何枚举区间？

比如样例：

\(4\)

\(-3\ 5\ 1\ 2\)

可以使用一种断环为链的操作，让其变成

\(-3\ 5\ 1\ 2\ -3\ 5\ 1\)

就有下面4个区间：

\(-3\ 5\ 1\ 2\)

\(5\ 1\ 2\ -3\)

\(1\ 2\ -3\ 5\)

\(2\ -3\ 5\ 1\)

容易写出代码

但很显然，对于\(10^{6}\)的数据会超时

将上面4个区间前缀和

\(-3\ 2\ 3\ 5\)

\(5\ 6\ 8\ 5\)

\(1\ 3\ 0\ 5\)

\(2\ -1\ 4\ 5\)

可以发现，只要区间最小值\(>=0\)，那么区间一定合法

就可以用单调队列优化时间复杂度

都知道，单调队列维护的是区间最小或最大值

刚好可以用来维护这道题长度为\(n\)的区间最小值

还有就是\(long\ long\)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e6 + 5;

#define int long long

int n, a[MAXN], sum[MAXN], ans;

deque <int> dq;

signed main() {

	scanf("%lld", &n);

	for (int i = 1; i <= n; ++i) scanf("%lld", a + i);

	for (int i = n + 1; i <= 2 * n - 1; ++i) a[i] = a[i - n]; //断环为链

	for (int i = 1; i <= 2 * n - 1; ++i) sum[i] = sum[i - 1] + a[i]; //前缀和

	for (int i = 1; i <= 2 * n - 1; ++i) {

		if (i > n) { //区间长度达到n了

			if (sum[dq.front()] - sum[i - n] >= 0) ++ans;

			if (dq.front() == i - n) dq.pop_front(); //如果是必须出队的那一个，就出队，否则就是后面的数，不用出队，因为还有机会

		}

		while (!dq.empty() && sum[i] <= sum[dq.back()]) dq.pop_back(); //单调队列的做法

		dq.push_back(i); //维护最小值的下标，才能统计区间和

	}

	if (sum[dq.front()] - sum[n] >= 0) ++ans; //最后还要统计一次

	printf("%lld\n", ans);

	return 0;

}

这题可以复习单调队列

巴特西

洛谷 P2629 好消息，坏消息（单调队列）

最新文章

热门文章