Codeforces Round 887 (Div. 2)

https://codeforces.com/contest/1853

E. Ina of the Mountain

题意

给出一个长度为 $n$ 的数组 $a$，满足 $1\leq a_i\leq k$。每次操作可以选定一个区间 $[l,r]$，让其中所有的数减 $1$。当一个数变成 $0$ 后，它会立刻变成 $k$。求最少需要多少次操作，才能让所有的数都变成 $k$。

题解

一道反悔贪心的题目，感觉很巧妙。

我们先考虑一个经典问题：给出一个数组 $a$，需要多少次同样的操作能将它变成全 $0$。答案是 $\sum\limits_{i=1}^n\max(0,a_i-a_{i-1})$。

这道题目相当于是可以给一些 $a_i$ 加上 $k$，求上述式子的最小值。我们考虑反悔贪心：

• 若 $a_i<a_{i-1}$，那么该项的贡献为 $0$。
• 若 $a_i>a_{i-1}$，有两种决策
  • 贡献为 $a_i-a_{i-1}$
  • 选取某个 $j<i$，给 $a_j,\cdots,a_{i-1}$ 都加上 $k$，贡献为 $a_j-a_{j-1}+k$。

我们用一个优先队列来维护所有可能的决策（也就是反悔堆），若 $a_i<a_{i-1}$，则将 $a_i-a_{i-1}+k$ 放入队列，否则将 $a_i-a_{i-1}$ 放入队列。这是因为我们选择反悔的位置 $j$ 一定满足 $a_j<a_{j-1}$，不然 $a_j-a_{j-1}+k$ 大于 $k$，得到的结果一定不会被选择。

补充说明：对于 $a_{i-1}$ 已经加上了 $k$，再取 $a_i-a_{i-1}$ 的决策，就相当于是给 $a_i$ 也加上了 $k$。

具体细节参考代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,k;cin>>n>>k;
        priority_queue<int,vector<int>,greater<int>> q;
        int lst=0;ll ans=0;
        for(int i=1;i<=n;i++)
        {
            int x;cin>>x;x%=k;
            if(x>lst)
            {
                q.push(x-lst);
                ans+=q.top();
                q.pop();
            }
            else q.push(k+x-lst);
            lst=x;
        }
        cout<<ans<<'\n';
    }
    return 0;
}