关于单调队列初始化
查看原帖
关于单调队列初始化
794083
Z3k7223ios::sync楼主2024/4/9 13:52

这份代码的初始化是 head = 1, tail = 0 (样例没过),但是提交喜提 10pts,只要把初始化改为 head = 1, tail = 1 就能 AC,求问原因,玄关感谢。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, k;
int a[N], sum[N], f[N][2];
int p[N], q[N], head = 1, tail;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		f[i][0] = max(f[i - 1][0], f[i - 1][1]);
		f[i][1] = q[head] + sum[i];
		while (head <= tail && q[tail] < f[i][0] - sum[i]) {
			--tail;
		}
		q[++tail] = f[i][0] - sum[i];
		p[tail] = i;
		while (head <= tail && p[head] < i - k + 1) {
			++head;
		}

	}
	cout << max(f[n][0], f[n][1]) << '\n';
	return 0;
}
2024/4/9 13:52
加载中...