社区讨论

过了，但是有些疑问

sssss41
P2034选择数字参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo8o9hak
此快照首次捕获于
2023/10/27 21:51
2 年前
此快照最后确认于
2023/10/27 21:51
2 年前
查看原帖
这是 0 pts 的代码
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;

int n, k, a[N], f[N], sum, head = 1, tail, q[N], p[N], ans;

signed main () {
    scanf ("%lld%lld", &n, &k);

    for (int i = 1; i <= n; ++ i) {
        scanf ("%lld", &a[i]);
        sum += a[i];
        f[i] = p[head] + a[i];
        while (head <= tail and p[tail] >= f[i]) tail --;
        q[++ tail] = i;
        p[tail] = f[i];
        while (head <= tail and q[head] < i - k) head ++;
    }

    for (int i = n - k; i <= n; ++ i)
        ans = max (ans, sum - f[i]);
    
    printf ("%lld\n", ans);

    return 0;
}
调了很久未果，直到机房另个人给我改了个小地方
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;

int n, k, a[N], f[N], sum, head = 1, tail = 1, q[N], p[N], ans;

signed main () {
    scanf ("%lld%lld", &n, &k);

    for (int i = 1; i <= n; ++ i) {
        scanf ("%lld", &a[i]);
        sum += a[i];
        f[i] = p[head] + a[i];
        while (head <= tail and p[tail] >= f[i]) tail --;
        q[++ tail] = i;
        p[tail] = f[i];
        while (head <= tail and q[head] < i - k) head ++;
    }

    for (int i = n - k; i <= n; ++ i)
        ans = max (ans, sum - f[i]);
    
    printf ("%lld\n", ans);

    return 0;
}
显然，单调队列的尾指针被初始化成 1，但是不太清楚它和 tail = 0 有什么区别，这两种写法哪种正确，如果这种正确的话，那我之前写的单调队列为什么可以过？

回复

共 2 条回复，欢迎继续交流。

正在加载回复...