题解 | #小红闯关#

分析

正向贪心难以计算, 倒序思考

对于当前位置, 假设获得了跳关的机会, 那么将在区间内能使用

很显然, 需要找到的最大花费的跳过, 可以使用最大堆实现

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, k;
LL a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    LL s = 0;
    for (int i = 0; i < n; ++i) cin >> a[i], s += a[i];

    priority_queue<LL> q;
    LL save = 0;
    for (int i = n - 1; i >= 0; --i) {
        if ((i + 1) % k == 0 && q.size()) {
            save += q.top();
            q.pop();
        }
        q.push(a[i]);
    }

    cout << s - save << '\n';
    return 0;
}