题解：CF1392F Omkar and Landslide

ssy666666 · 2026-07-21 16:34:39 · 题解

UPD 2026/07/23: 被 hack，加入了负数取模。

首先这个 h_j + 2 \le h_{j + 1} 看起来不好处理，如果把 +2 转化为 +1，看起来就会好做一点。因此，一个经典套路：设 g_j = h_j - j，那么考虑对于 g 进行操作，最后还原成 h。

首先，这个序列变为了单调不减，再看到原来的“滑坡”，此时变为了若 g_j + 1 \le g_{j + 1}，即 g_j < g_{j + 1}，则将 g_j 加一，g_{j+1} 减一。

我们定义一个“连续段 [l,r]”表示 \forall i \in [l,r],j \in [l,r],g_i=g_j 且 g_{l-1} \ne g_l,g_{r+1} \ne g_r。定义连续段的值为 g_l。

我们先考虑问题的简化版。

如果只有两个连续段，并且后一个连续段的值比前一个大 1。比如：

手玩一下，我们定义 g^i 表示经过 i 分钟的“滑坡”后 g 的结果。那么有：

可以看到，原本较大的连续段好像在向左“传递”，最后两段会交换位置。证明比较容易。设第一段为 [1,p]，第二段为 [p+1,n]，考虑连续的两个第二段的点 g_l,g_{l+1}，当 g_l \rightarrow g_l - 1 前，g_{l+1} 不会滑坡，直到变化后，在下一轮 g_{l+1} 会向 g_l 滑坡，这个过程会一直持续直到无法再向左滑坡，也就是两个连续段位置完全交换后。

考虑若两段的差值不为 1 呢？同样设第一段为 [1,p]，第二段为 [p+1,n]，

第一分钟 g_{p+1} 会向 g_p 滑坡；

第二分钟依次 g_{p+2} 会向 g_{p+1} 滑坡，g_{p+1} 会向 g_p 滑坡，g_p 会向 g_{p-1} 滑坡。这个过程其实相当于 g_{p+2} 高度减一，g_{p-1} 高度加一。

依次地，这样也会有一个类似于“传递”的过程，并且该过程可能不止在 1 分钟内完成。

同样的道理，拓展到多段仍然成立。所有段最后一定会合并为两段，并且前一段比后一段的值大 1。

需要注意的是，我代码中的 sum 有可能小于 0，需要特殊处理一下。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 1e6 + 7 ;

int h[MAXN] ;
signed main() {
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int n ;
    cin >> n ;
    int sum = 0 ;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> h[i] ;
        sum += h[i] - i ;
    }

    int w = sum / n ;
    int p = sum % n ;
    if (p < 0)  p += n , w -- ;
    for (int i = 1 ; i <= p ; i ++) {
        cout << w + 1 + i << " " ;
    }
    for (int i = p + 1 ; i <= n ; i ++) {
        cout << w + i << " " ;
    }

    return 0 ;
}