F. Omkar and Landslide - 题解

比赛与标签

比赛: Codeforces Global Round 10 标签: binary search, constructive algorithms, data structures, greedy, math 难度: *2400

题目大意喵~

你好呀，各位算法探险家！今天我们来解决一个非常有趣的问题，关于一座正在发生山体滑坡的 Celeste 山，喵~

题目是这样的：我们有一座山，从山脚到山顶有 n 个观测点。在第 j 个观测点，山的高度是 h_j。一开始，山的高度是严格递增的，也就是 h_1 < h_2 < ... < h_n。

突然，山体滑坡开始啦！每一分钟，只要存在某个位置 j 满足 h_j + 2 <= h_{j+1}，那么就会有一立方的土从 j+1 的位置滑到 j 的位置。这会导致 h_j 增加 1，而 h_{j+1} 减少 1。这个过程对所有满足条件的位置是同时发生的哦。

当不再有任何位置 j 满足 h_j + 2 <= h_{j+1} 时，山体滑坡就停止了。我们的任务就是，算出滑坡停止后，这 n 个位置的最终高度是多少，的说。

输入会给我们 n 和初始的 n 个高度，我们需要输出最终的 n 个高度。

解题思路大揭秘！

呀吼~ 看到这种描述一个过程，然后求最终状态的题目，很多同学的第一反应可能是模拟！但是呐，n 最大有 10^6，高度也很大，模拟每一分钟的变化肯定会超时的说。所以，我们必须找到更聪明的办法，喵！

这通常意味着我们要从过程的最终状态入手，或者寻找整个过程中的不变量。

关键性质一：总量守恒！

我们来观察一下山体滑坡的过程：一立方的土从 j+1 移动到 j。这意味着 h_{j+1} 减 1，h_j 加 1。对于整个系统来说，土的总量是不是没有变呢？是的！无论土怎么滑来滑去，所有位置的高度总和 S = h_1 + h_2 + ... + h_n 是一个不变量！这可是一个超级重要的发现呐！

关键性质二：最终会长成什么样？

滑坡停止的条件是：对于所有的 j（从 1 到 n-1），都满足 h_j + 2 > h_{j+1}。因为高度都是整数，这等价于 h_{j+1} - h_j <= 1。

这告诉我们，在最终状态下，任意两个相邻位置的高度差最多是 1！也就是说，最终的高度序列 a_1, a_2, ..., a_n 一定满足 a_{j+1} - a_j 的值只能是 0 或者 1。这样的序列看起来会非常“平滑”，就像一个平缓的斜坡，比如 5, 5, 6, 7, 7, 8 这样。

数学建模时间！

好戏登场了喵！我们来用一点点数学魔法把问题变得更简单。

为了方便计算，我们使用 0-based 索引，即最终高度为 a_0, a_1, ..., a_{n-1}。 我们知道两个性质：

1. sum(a_i) = S (S 是初始总高度)
2. a_{i+1} - a_i 是 0 或 1。

现在，我们引入一个神奇的变换。令 b_i = a_i - i。我们来看看 b 序列有什么特点： b_{i+1} - b_i = (a_{i+1} - (i+1)) - (a_i - i) = (a_{i+1} - a_i) - 1

因为 a_{i+1} - a_i 是 0 或 1，所以 b_{i+1} - b_i 就只能是 -1 或 0 了！ 这意味着 b_{i+1} <= b_i。哇！b 序列是一个非递增的整数序列！问题一下子变得清晰多了。

求解 b_i 序列

我们已经知道 b 序列是非递增的，那它的总和是多少呢？ S = sum(a_i) = sum(b_i + i) = sum(b_i) + sum(i)sum(i) 对于 i 从 0 到 n-1，就是 0 + 1 + ... + (n-1)，这是一个等差数列求和，结果是 T = n * (n-1) / 2。 所以，sum(b_i) = S - T。

现在问题转化为：找到一个长度为 n 的非递增整数序列 b_0, b_1, ..., b_{n-1}，使得它们的总和为 S - T。

要构造一个总和固定、并且非递增的序列，最“均匀”的分配方式就是最好的。我们可以先把 S - T 平均分配给 n 个 b_i：

• 每个 b_i 的基础值是 base = (S - T) / n (整除)。
• 还剩下一些余数 extra = (S - T) % n。

这 extra 个 "1" 应该加给谁呢？因为 b 序列是非递增的，所以较大的值必须放在前面。因此，我们将这 extra 个 "1" 分配给前 extra 个元素。

• 对于 i < extra，b_i = base + 1。
• 对于 i >= extra，b_i = base。

还原最终答案！

我们已经求出了 b_i 序列，现在只要用 a_i = b_i + i 把它变回最终的高度序列 a_i 就大功告成啦！

• 如果 i < extra (前 extra 个位置): a_i = b_i + i = (base + 1) + i。
• 如果 i >= extra (剩下的位置): a_i = b_i + i = base + i。

这就是最终的答案公式！我们完全绕过了复杂的模拟过程，通过分析不变量和最终状态，直接得出了结果，是不是很酷，喵~

代码实现喵~

#include <iostream>

using namespace std;

int main() {
    // 使用高速 IO，对付大数据量是基本操作哦，喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    // 计算初始山体的总高度 S。
    // 注意！h_i 和 n 都很大，S 可能会超过 int 的范围，必须用 long long！
    long long S = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        S += x;
    }

    // 计算 0 + 1 + ... + (n-1) 的和，也就是我们推导中的 T
    long long T = (long long) n * (n - 1) / 2;

    // 根据公式 sum(b_i) = S - T，计算 b_i 序列的平均基准值 base
    long long base = (S - T) / n;
    
    // 计算需要额外分配的 "1" 的数量，也就是余数 extra
    long long extra = S - base * n - T;

    // 循环输出最终的 n 个高度 a_i
    for (int i = 0; i < n; i++) {
        // 对于前 extra 个位置，它们分到了一个额外的 "1"
        if (i < extra) {
            // a_i = base + i + 1
            cout << base + i + 1;
        } else {
            // 其他位置就是基准值
            // a_i = base + i
            cout << base + i;
        }
        
        // 输出格式要求，除了最后一个数，后面都要有空格
        if (i < n - 1) {
            cout << ' ';
        }
    }
    cout << '\n';

    return 0;
}

喵喵复杂度分析

• 时间复杂度: O(n) 的说。我们只需要一次循环读入 n 个数并计算总和 S，然后再一次循环输出 n 个结果。中间的计算都是常数时间 O(1) 的。所以总的时间复杂度是线性的，非常高效！
• 空间复杂度: O(1) 的说。我们只用了几个 long long 变量来存储 n, S, T, base, extra 等。我们不需要把所有的高度都存起来，所以空间消耗非常小，和 n 的大小无关。

知识点与总结

这次的解题之旅是不是收获满满呀？我们来总结一下关键的知识点和技巧吧！

1. 不变量思想: 在分析一个动态变化过程的题目时，首先要思考什么东西在变化中是保持不变的。本题中的“总土量守恒”（即高度总和 S 不变）就是解题的突破口！
2. 终态分析: 当模拟过程太复杂时，直接分析过程结束时的稳定状态有什么性质，是另一个强大的武器。本题的终态是 a_{i+1} - a_i <= 1，这直接定义了答案的结构。
3. 巧妙的数学变换: b_i = a_i - i 这种变换非常经典，它可以把一个关于“差分”的约束（a_{i+1} - a_i 是 0 或 1）转换成一个关于“单调性”的约束（b_i 非递增）。以后遇到类似的序列问题，可以尝试一下哦！
4. 均分思想: “总和固定，分配给 n 个数，并满足单调性”，这类问题通常可以用“求平均，分余数”的贪心思想来解决。这在构造性问题中非常常见。
5. 注意数据范围: n 和 h_i 的值都很大，它们的乘积会非常非常大，一定要记得使用 long long 来防止数据溢出，不然就会得到一个 Wrong Answer 的悲伤结局啦，喵~

希望这篇题解能帮助你理解这个问题！继续加油，在算法的世界里不断探索吧，呐！