[CF1392F] Omkar and Landslide - 结论,构造

Description

现在有一些山发生了山体滑坡，这些山从左到右依次排布，第 \(i\) 座山的高度为 \(h_i\)，且 \(\forall i\in [1,n),h_i<h_{i+1}\)。每一轮滑坡中，假如变化前的 \(h_i+2\leq h_{i+1}\)，那么两座山的高度会发生变化，即 \(h_i+1,h_{i+1}-1\)，本轮中所有位置的变化是同时的。问无穷轮后，每座山的高度是多少。

Solution

先讨论问题的三个性质：①操作的顺序无关性；②末态下相邻差不超过 \(1\)；③末态下相邻相等的对数不超过 \(1\)。

Proof. 考虑这样一种方法，每次取第 \(i\) 个元素开始向左推进，若 \(i=1\) 或者 \(h_i - h_{i-1}<2\) 则结束，否则修改 \(h_i,h_{i-1}\) 并继续向左推进。
在这样一轮推进中，若 \(i\) 左侧的数字各不相同，则会一直推进到 \(1\)，这样可能会使得相等的对数增加 \(1\)；否则，推进操作会在 \(i+1\) 的右边结束，可能会使得相等对数减少 \(1\)。

于是 \(S=\sum h_i\) 和 \(n\) 两个参数即确定了一个唯一的答案序列。

暴力构造这个答案序列的方法是：从序列 \(0,1,2,...,n-1\) 开始，每次暴力对序列的一个尽可能长的前缀增加 \(1\)。

结论为

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int n,a[N],s;

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) s+=a[i];

    for(int i=1;i<=n;i++)
    {
        int tmp=(i-1)+(s-n*(n-1)/2)/n+(i<=((s-n*(n-1)/2)%n));
        cout<<tmp<<" ";
    }
    cout<<endl;

    return 0;
}

[CF1392F] Omkar and Landslide - 结论,构造

原文：https://www.cnblogs.com/mollnn/p/13766421.html