题解：CF2085D Serval and Kaitenzushi Buffet

__Hollow_Knight__ · 2026-10-21 17:58:53 · 题解

::::info[题面大意]{open} 共有 n 盘寿司，每盘寿司都有 k 块，取这盘寿司需要花费 1 的时间，吃 1 个寿司也需要 1 的时间，吃完第 i 盘寿司可以获得 d_i 的美味值。

每当一盘寿司转到你面前时，将会获得 1 的时间。

::::info[思路]{open} 首先考虑贪心，发现不可做；然后考虑反悔贪心，发现将题面倒过来变的可做。 :::warning[为什么要倒过来做]{open} 很明显我们要维护时间，但是时间是不断少，选择是困难的。

::::success[Code]

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL N = 2e5+10 , Inf = 0x7f7f7f7f;
int n , k;
LL d[N];
priority_queue<LL , vector<LL> , greater<LL>> q; //用小根堆维护
inline void solve(){
    LL now = 0 , ans = 0;
    while(!q.empty()) q.pop(); //多测记得清空
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++) cin >> d[i];
    for(int i = n ; i >= 1 ; i--){
        now++;
        now -= k+1; //吃和拿的时间为 k+1
        ans += d[i];
        q.push(d[i]);
        while(now < 0){ //反悔操作
            now += k+1;
            ans -= q.top();
            q.pop();
        } 
    }
    cout << ans << "\n";
}
signed main(){
    int T; cin >> T;
    while(T--){
        solve();
    }
    return 0;
}