题解 Ina of the Mountain

· · 题解

CF1852C Ina of the Mountain 题解

首先将题目进行一定的转化，注意到对于一个章鱼（数字）a_i，我们可以执行 (a_i \mod k) + mk 次操作来使其符合条件（n 为非负整数）。当确定了每个章鱼需要被执行的操作次数后，我们便可以容易地得出答案。

假设确定了每个章鱼需要被执行的操作次数为 [1, 2, 3, 0, 2, 4]，如下图所示，总共需要执行的操作次数即为红线标出的总长度，即 1 + 1 + 1 + 2 + 2 = 7。

不妨将每个章鱼的取值看作高度，将一个章鱼需要被操作的次数加上 k 称作提升。同时，由题意，高度恰好等于 k 的章鱼可以视为高度为 0，在下文中默认将所有高度恰好为 k 的章鱼的高度看作 0。

假设已经确定了 i 个章鱼需要被操作的次数，考虑第 i + 1 个章鱼，将第 i 个章鱼的高度记作 h_i。

  1. 若 h_{i+1} \le h_i，那么可以直接不做任何提升操作。

  2. 若 h_{i + 1} \gt h_i，有以下两种选择：

    • 不做任何抬升操作，将答案增加 h_{i + 1} - h_{i}；
    • 选择一个 j \le i，使得 h_j + k - h_{j- 1} - \max(0, h_j - h_{j - 1}) 最小（这个最小值后文记作 \Delta_i），并提升 [j, i] 范围中的每个章鱼，将答案增加 \Delta_i。

第一种操作很好理解，第二种操作的思想是将新增的章鱼前的章鱼提升，使得新增的章鱼不对答案产生贡献。同时，容易得知，如果选定一个章鱼，并将其及其后所有章鱼提升，其后章鱼产生的贡献不变，只有被选定的章鱼贡献产生变化。可参考下图。

在两种操作中选择一个贡献较小的，就完成了第 i + 1 个章鱼的计算。

这里按照这个思路直接模拟两种操作即可，不提供参考代码。

然而，每新增一个章鱼，这种方法就要向前遍历每一个章鱼，时间复杂度为 O(n^2)，无法通过此题。

优先队列优化

注意到，在上面的方法中，每个 j 最多被选中一次，且选择任意一个 j 进行操作后都不会影响其他任意一个 \Delta_i。那么，在每次新增一个章鱼后，我们可以预先计算好这个章鱼的 \Delta_i，并将其压入一个优先队列，这样之后的查询可以以 O(1) 的复杂度完成。同时，由于每个 j 最多被选中一次，当我们通过优先队列获取到对应的 j 后，只需要将其出队而不需重新计算并入队。

引入优先队列进行优化后，每个章鱼需要花费 O(\log{n}) 的时间计算 \Delta_i 并入队，另外还可能需要 O(\log{n}) 的时间出队。总体时间复杂度为 O(n \log{n})，使用的额外空间主要来自优先队列，空间复杂度 O(n)。

参考代码

void work()
{
    int n, k;
    cin >> n >> k;
    vector<int> arr(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        arr[i] %= k;
    }
    priority_queue<long long, vector<long long>, greater<long long>> q;
    long long ans = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        if (arr[i - 1] == arr[i]) continue;
        if (arr[i - 1] > arr[i])
        {
            q.push(arr[i] + k - arr[i - 1]);
        }
        else // arr[i - 1] < arr[i]
        {
            q.push(arr[i] - arr[i - 1]);
            ans += q.top();
            q.pop();
        }
    }

    cout << ans << endl;
}