题解 | 小红闯关

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 这道题关键洞察在于跳关工具均位于k的倍数关卡, 而跳关工具具备时效性，只能对未来的关卡施加影响
// 因此我们不妨从后往前遍历，让元素加入优先队列（自动降序的队列），然后如果遇到了k的倍数关卡，
// 那么就意味着我们能将优先队列队头的元素（耗时最长且还未完成的关卡）取出，
// 同时不断将当前遍历的元素压入优先队列，以上这一次遍历就能求出总节省下来的时间

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> s1(n);
    long long total_time = 0;
    for (int i = 0; i < n; i++) {
        cin >> s1[i];
        total_time += s1[i];
    } // 一次遍历，读入元素，得到原始总消耗时间

    long long save_time = 0;
    priority_queue<long long> s2;
    for (int i = n-1; i >= 0; i--) {
        if ((i+1) % k == 0 && !s2.empty()) {
                save_time += s2.top();
                s2.pop();
        }
        s2.push(s1[i]);        
    } // 二次遍历，得到总节省时间

    cout << total_time - save_time;    
}