题解：CF1392F Omkar and Landslide

wmrqwq · 2025-09-26 21:15:56 · 题解

题目链接

CF1392F Omkar and Landslide (*2400)

解题思路

结论题，最终的序列只与 \displaystyle \sum_{i=1}^{n} a_i 的值有关。

大致证明就是，首先这个序列是单调不降的，并且，对于任意 i \in [1,n)，都有 a_{i+1}-a_i \le 1，那么容易得出最终序列是个固定值。

那么可以刻画成以下的问题，初始有一个 b 序列为 [0,1,2,\dots,n-1]，你需要进行 m 次操作，每次给在满足以下两个的情况下的最左边的数 +1：

• 将这个数 +1 后，序列依然单调不降。
• 将这个数 +1 后，序列任意两个数差值不超过 1。

这个贪心是容易做的，总时间复杂度 O(n)。

参考代码

ll n,S;
ll a[1000010];
ll b[1000010];
//tulpa
void _clear(){}
void solve()
{
    _clear();
    cin>>n;
    forl(i,1,n)
        cin>>a[i],
        S+=a[i]-i+1,
        b[i]=i-1;
    // cout<<S<<endl;
    ll num=S/n;
    forl(i,1,n)
        b[i]+=num;
    S-=num*n;
    forl(i,1,n)
        if(S)
            b[i]++,
            S--;
    forl(i,1,n)
        cout<<b[i]<<' ';
    cout<<endl;
}