题解 | 小红闯关

贪心，1 尽量将道具用在花费时间大的关卡  2 对于你想要用道具的关卡，尽量用离这个关卡前面最近的道具 比如你想在第6关使用道具，第3关和第5关各获得一个道具，那么用第5关的道具
#include <bits/stdc++.h>
using namespace std;
int main() {
    // 5 4 4 1 1 1
    // 4 6 3 5 2 1
    // 5 3
    int n, k;
    cin >> n >> k;
    set < int, greater<> > se;
    map <int, vector<int> , greater<> > ma;
    for (int i = 1, j = 1; i <= n; i++) {
        int x;
        cin >> x;
        ma[x].push_back(i);
        if (i == k * j + 1) {
            se.insert(i);
            j++;
        }
    }
    long long int ans = 0;
    for (auto it : ma) {
        for (int i = it.second.size() - 1; i >= 0; i--) {
            int nowi = it.second[i];
            int nowx = it.first;
            //for(auto ik:se) cout<<ik<<' ';cout<<'\n';
            if(se.size() == 0 || *se.rbegin() > nowi) {
                ans += nowx;
                //cout<<"1:"<<nowi<<","<<nowx<<'\n';
                continue;
            }
            se.erase( se.lower_bound(nowi) );
            //cout<<"2:"<<nowi<<","<<nowx<<'\n';
        }
    }
    cout<<ans<<'\n';
    return 0;
}