Codestudio Weekend Contest 56 - Ninja And The Challenge

Problem

给一个序列，一次操作可以使得任意元素+1/-1，问最少多少次操作可以使得整个序列递增或递减？

Solution

能否只构造成递增来解决？

当然可以，如果想要构造成递减，只需要把序列逆序，然后构造成递增。

假设我们只有 2 个数字 [10, 6]，那么我们可以将 6 向上移动 4 步或 10 向下移动 4 步；无论哪种方式，成本都是 4。同时，以同样的成本，我们还可以制作 [7, 7] 或 [8, 8] 或 [9, 9] 或 [10, 10]。

假设我们支付了 4 的成本并使其成为 [10, 6] → [6, 6]，并且由于我们已经支付了成本，以后如果我们改变主意，我们可以自由地向上移动 [6, 6]到 [7, 7], [8, 8], …, 无需额外费用，因为 [7, 7], [8, 8],[9, 9]… 都需要我们已经支付的 4 个步骤. 数字 [6, 6] 现在向上自由。

一个向上的自由数字可以自由上升直到它之前的最大数字，并作为它的最低值存储。对于每个数字，我们找到它的向上空闲数并制作向上空闲数组。保证我们总是可以使用这个更新的空闲数组来增加数组。

例如，如果向上自由数组是 [1, 7, 6, 3]，我们可以创建一个零成本的递增数组 [1, 7, 7, 7]，因为最后 6, 3 是向上自由的。

如果下一个数是5，那么我们以2为代价减少7→5，新的向上自由数组变为[1,7,6,3]→[1,5,6,3,5]，而这个数组可以成为零成本的递增序列 [1, 5, 6, 6, 6]。

总之，如果新数字大于迄今为止最大的向上自由数字，则追加它，因为序列已经在增加。但如果不是，则以差值为代价，将最大的向上自由数减少到与新数相同；这两个数字现在都向上免费了。第二大数字现在成为新的高度。

我们使用最大堆来存储这些向上的空闲数，以在 O(log(n)) 时间内找到最大的一个。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
##include "bits/stdc++.h"
using namespace std;

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

int solve(std::vector<int>& nums) {
    int ans = 0;
    std::priority_queue<int> pq;
    for (const int& x : nums) {
        if (!pq.empty() && pq.top() > x) {
            ans += pq.top() - x;
            pq.pop();
            pq.push(x);
        }
        pq.push(x);
    }
    return ans;
}

int minimumMovesToSort(int n, vector<int> &a) {
    std::vector<int> b(a.rbegin(), a.rend());
    return std::min(solve(a), solve(b));
}

/*
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    return 0;
}
*/

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2023/01/14/codestudio-weekend-contest-56-ninja-and-the-challenge/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！