题目

暴力 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int a[N];
int main()
{
    int n, k;
    cin >> n >> k;

    ll sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];

    int minn = 1e9, pos;
    ll cnt = 0;
    int l = 1, r;
    while (r = l + k - 1, r <= n)
    {
        for (int i = l; i <= r; i++)
        {
            if (a[i] <= minn)
            {
                minn = a[i];
                pos = i;
            }
        }
        for (int i = l; i <= r; i++)
        {
            a[i] -= minn;
        }
        cnt += minn;
        l = pos + 1;
        minn = a[pos + 1];
    }

    cout << sum - cnt * k + cnt;
}

线段树优化 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
int a[N];
struct node
{
    int l, r;
    int m, p, lazy;
} tr[4 * N];
void pushup(node &u, node &l, node &r)
{
    if (l.m == r.m)
    {
        u.m = l.m;
        u.p = max(l.p, r.p);
    }
    else if (l.m < r.m)
    {
        u.m = l.m;
        u.p = l.p;
    }
    else
    {
        u.m = r.m;
        u.p = r.p;
    }
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(node &u, node &l, node &r)
{
    if (u.lazy)
    {
        l.m = max(l.m + u.lazy, 0);
        r.m = max(r.m + u.lazy, 0);
        l.lazy += u.lazy;
        r.lazy += u.lazy;
        u.lazy = 0;
    }
}
void pushdown(int u)
{
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if (l == r)
        tr[u] = {l, r, a[l], l};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int l, int r, int d)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].lazy += d;
        tr[u].m = max(tr[u].m + d, 0);
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, d);
    if (r > mid)
        modify(u << 1 | 1, l, r, d);
    pushup(u);
}
node query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u];

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid)
        return query(u << 1, l, r);
    else if (l > mid)
        return query(u << 1 | 1, l, r);
    else
    {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        node ans;
        pushup(ans, left, right);
        return ans;
    }
}
int main()
{
    int n, k;
    cin >> n >> k;

    ll sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];

    build(1, 1, n);

    int l = 1, r;
    ll cnt = 0;
    while (r = l + k - 1, r <= n)
    {
        auto u = query(1, l, r);
        int minn = u.m;
        cnt += minn;
        modify(1, l, r, -minn);
        l = u.p + 1;
    }

    cout << sum - k * cnt + cnt;
}

单调队列优化 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
deque<ll> q;
int n, k, pos;
ll a[1000005], ans, d;

int main()
{
    scanf("%d%d", &n, &k);
    pos = k;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        ans += a[i];
        a[i] += d; // a[i]要放入队列时，加上偏移量
        while (q.size() && a[q.back()] >= a[i])
            q.pop_back();
        q.push_back(i);
        if (i >= pos)
        {
            ll v = a[q.front()] - d; // 队首的值减去偏移量才是真实值
            pos = q.front() + k;
            q.pop_front();
            ans -= v * (k - 1);
            d += v;
        }
    }
    printf("%lld", ans);
    return 0;
}