题解：CF2085D Serval and Kaitenzushi Buffet

ZMQ_Ink6556 · 2025-03-23 11:34:33 · 题解

题解：CF2085D Serval and Kaitenzushi Buffet

题意简述

Serval 刚刚找到了一家 Kaitenzushi 自助餐厅。 Kaitenzushi 的意思是餐厅里有一条传送带，将寿司盘送到顾客 Serval 面前。

在这家餐厅，每个盘子里正好有 k 块寿司，第 i 个盘子有一个美味值 d_i。

Serval 将在这家餐厅吃 n 分钟，在 n 分钟内，他必须吃完他从腰带上拿来的所有寿司。

将未吃掉的寿司片的数量表示为 r。 最初，r = 0。在第 i 分钟 (1 \le i \le n)，只有第 i 盘寿司会送到 Serval 面前。

他可以执行以下操作之一：

• 从传送带上拿出第 i 盘寿司（其美味是 d_i），r 将增加 k。
• 吃掉他之前从腰带上拿走的一块未吃的寿司，r 将减少 1。请注意，只有在 r > 0 时才能这么做。
• 或者，什么都不做，r 将保持不变。

请注意，在 n 分钟后，r 的值必须为 0。

Serval 想把他吃的所有盘子的美味总和最大化。帮他找出来！

解题思路

容易发现在 n - k、n - 2k、n - 3k \cdots 时获取寿司是一种合法的方案（不一定最优）。

考虑贪心，将一个合法寿司换成一个更早的寿司也一定合法，但换成更晚的不一定合法。

可以观察到，在 n - k、n - 2k、n - 3k \cdots 时获取寿司是一种边界方案，也就是说，若将这些寿司标记为合法，那么将一个合法寿司换成一个更早的寿司也一定合法，但换成更晚的一定不合法。

此时从左到右贪心，每遇到标记点从前面取出一个美味度最大的寿司即可通过。

单次取最大值操作可以通过优先队列 O(\log n) 实现。

复杂度：O((n + k) \log n)。

参考代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int t;
long long k , n , d[200005] , dp[200005] , ans;
bool vis[200005];
priority_queue<long long> q;
int main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        for(int i = 1 ; i <= n * 2 ; i++)
        {
            dp[i] = -1000000000000000018ll;
        }
        dp[n + 1] = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> d[i];
            vis[i] = 0;
        }
        for(int i = n ; i >= 1 ; i--)
        {
            if(dp[i + k + 1] == 0)
            {
                dp[i] = 0;
                vis[i] = 1;
            }
        }
        ans = 0;
        while(q.size())
        {
            q.pop();
        }
        for(int i = 1 ; i <= n ; i++)
        {
            q.push(d[i]);
            if(vis[i])
            {
                ans += q.top();
                q.pop();
            }
        }
        cout << ans << '\n';
    }
    return 0;
}